C++で解く「Lonely Pixel II」― 条件を満たす黒ピクセルを数えるアルゴリズムと実装例

問題の概要

白（W）と黒（B）のピクセルで構成された画像が与えられ、特定の条件を満たす「孤独な黒ピクセル」の総数を求めるのがこの問題の目的です。対象となるのは行R・列Cの位置にある黒ピクセルで、次の2つのルールをすべて満たしている必要があります。

• 行Rと列Cには、それぞれちょうどN個の黒ピクセルが含まれていること
• 列Cに黒ピクセルを持つすべての行が、行Rと完全に同一であること

画像は「B」（黒）と「W」（白）からなる2次元のchar型配列として表現されます。

入力例

N = 3 のとき、出力は 6 になります。これは1列目と3列目（0始まり）に存在するすべての「B」が条件を満たすためです。

たとえば、行R = 0、列C = 1 の「B」に注目してみましょう。

• ルール1： 行0には黒ピクセルがちょうど3個あり、列1にも黒ピクセルがちょうど3個存在します。
• ルール2： 列1に黒ピクセルを持つ行は行0・行1・行2の3つだけで、これらはすべて行0と完全に一致しています。

解法の考え方

この問題は、各黒ピクセルの位置情報を事前に整理しておくことで効率的に解けます。手順は以下の通りです。

1. 答えを格納する変数 ret を 0 で初期化します。
2. 2つのマップを用意します。r[i] は「行iに含まれる黒ピクセルの列番号の集合」、c[j] は「列jに含まれる黒ピクセルの行番号の集合」です。
3. n を画像の行数、m を列数とします。
4. まず全マスを走査し、p[i][j] が 'B' であれば r[i] に j を、c[j] に i を登録します。
5. 再度全マスを走査し、p[i][j] が 'B' かつ r[i] のサイズが N、c[j] のサイズが N と等しい場合、列jに黒ピクセルを持つすべての行 x について r[x] と r[i] が一致するかを確認します。1つでも異なる行があれば不成立、すべて一致していれば ret を1増やします。
6. 最後に ret を返します。

C++による実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findBlackPixel(vector<vector<char>>& p, int N) {
        int ret = 0;
        unordered_map<int, set<int>> r, c;
        int n = p.size();
        int m = p[0].size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(p[i][j] == 'B'){
                    r[i].insert(j);
                    c[j].insert(i);
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m && r.count(i); j++){
                if(p[i][j] == 'B' && r[i].size() == N && c[j].size() == N){
                    bool ok = true;
                    for(auto& x : c[j]){
                        if(r[x] != r[i]){
                          ok = false;
                          break;
                       }
                    }
                    ret += ok;
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<char>> v = {{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','W','B','W','B','W'}};
    cout << (ob.findBlackPixel(v, 3));
}

入力

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

出力

6

計算量の目安

前処理で全マスを走査するのに O(n×m)、判定フェーズでは各候補ピクセルに対して最大 N 行分の比較が発生するため、全体の計算量は O(n×m×N) 程度になります。unordered_map と set を組み合わせることで、行同士の一致判定も高速かつ簡潔に実装できるのがポイントです。