C++で黒く塗られた正方形の中心を見つける方法

n × m のサイズを持つ行列を考えます。各セルは白を表す「W」または黒を表す「B」のいずれかです。この表の中には、奇数の辺の長さを持つ正方形が黒く塗られており、その正方形の中心を見つけることが課題となります。

問題の例

例えば、以下のような入力が与えられたとします。

この場合、出力は (3, 1) となります。これは、黒い正方形の中心セルが「1行目・3列目」に位置しているためで、結果は（列, 行）の順で出力されます。

解法のアプローチ

この問題は、黒いセル（'B'）の座標の平均を計算することで解けます。黒く塗られた正方形は上下左右に対称な図形であるため、すべての黒セルの行インデックスの平均と列インデックスの平均は、それぞれ正方形の中心の行・列と一致します。

アルゴリズムの手順

1. 行列の行数 n と列数 m を取得する。
2. 黒セルの個数 cnt と、座標の累積値 X・Y を 0 で初期化する。
3. すべてのセルを走査し、'B' であれば cnt を 1 増やし、X に行番号 i、Y に列番号 j を加算する。
4. X を cnt で、Y を cnt で割り、中心座標を求める。
5. (Y, X) の順で結果を返す。

計算量は行列の全セルを一度走査するだけなので O(n × m) となり、非常に効率的です。

n := 行列の行数
m := 行列の列数
cnt := 0
X := 0
Y := 0
i を 0 から n 未満まで 1 ずつ増やしながら繰り返す:
    j を 0 から m 未満まで 1 ずつ増やしながら繰り返す:
        もし matrix[i, j] が 'B' と等しいならば:
            cnt を 1 増やす
            X := X + i
            Y := Y + j
X := X / cnt
Y := Y / cnt
return (Y, X)

C++による実装例

それでは、理解を深めるために実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<char>> matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    int cnt = 0, X = 0, Y = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
            if (matrix[i][j] == 'B')
                cnt++, X += i, Y += j;
    }
    X /= cnt;
    Y /= cnt;
    printf("%d, %d\n", Y, X);
}
int main(){
    vector<vector<char>> matrix = { { 'W', 'W', 'B', 'B', 'B', 'W' },
        { 'W', 'W', 'B', 'B', 'B', 'W' }, { 'W', 'W', 'B', 'B', 'B', 'W' },
        { 'W', 'W', 'W', 'W', 'W', 'W' }, { 'W', 'W', 'W', 'W', 'W', 'W' } };
    solve(matrix);
}

入力

{ { 'W', 'W', 'B', 'B', 'B', 'W' },
    { 'W', 'W', 'B', 'B', 'B', 'W' }, { 'W', 'W', 'B', 'B', 'B', 'W' },
    { 'W', 'W', 'W', 'W', 'W', 'W' }, { 'W', 'W', 'W', 'W', 'W', 'W' } }

出力

3, 1