C++で解くLonely Pixel I：孤独な黒ピクセルを数えるアルゴリズム

白と黒のピクセルで構成された画像が与えられ、その中に含まれる「孤独な黒ピクセル（Black Lonely Pixel）」の数を求める問題を考えます。画像は2次元のchar型配列として表現され、各要素は黒ピクセルを表す 'B'、白ピクセルを表す 'W' のいずれかです。

ここで孤独な黒ピクセルとは、その位置と同じ行・同じ列に他の黒ピクセルが一切存在しない 'B' のことを指します。

例として、次のような入力が与えられたとしましょう。

このとき出力は 3 となります。3つの 'B' はいずれも、自分の属する行にも列にも他の黒ピクセルを持たないため、すべてが孤独ピクセルと判定されるからです。

解法のアプローチ

この問題は、次の手順で効率よく解くことができます。

• 各行の黒ピクセル数を記録する配列 rowCount（サイズn）と、各列の黒ピクセル数を記録する配列 colCount（サイズm）を用意します。
• 1回目の走査で画像全体を調べ、'B' を見つけるたびに、そのセルが属する行と列のカウンターをそれぞれ増やします。
• 2回目の走査では、セル (i, j) が 'B' であり、かつ rowCount[i] と colCount[j] がどちらも1である場合、そのピクセルは孤独な黒ピクセルであると判断し、答えを1つ増やします。
• 最後に累積したカウントを結果として返します。

C++による実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = n ? picture[0].size() : 0;
        vector<int> rowCount(n, 0);
        vector<int> colCount(m, 0);

        // 各行・各列に含まれる黒ピクセルの数をカウント
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }

        // 行・列の両方で唯一の黒ピクセルを数える
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) {
                    ret++;
                }
            }
        }
        return ret;
    }
};
int main() {
    Solution ob;
    vector<vector<char>> v = {{'W','W','B'},{'W','B','W'},{'B','W','W'}};
    cout << ob.findLonelyPixel(v) << endl;
}

入力

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

出力

3

計算量の目安

時間計算量は O(n×m)、空間計算量は O(n+m) です。画像を2回走査するだけで判定が完了するため、大きな入力サイズに対しても効率的に処理できるのがこの手法のポイントです。