533. Lonely Pixel II

Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:

1. Row R and column C both contain exactly N black pixels.

2. For all rows that have a black pixel at column C, they should be exactly the same as row R

The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

Example:

Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']] 

N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

1. The range of width and height of the input 2D array is [1,200].

題目的意思是要找到一個'B' grid，他的同一個row上和同一個col上，都有N個'B'。而且沿著col上下要有N個row長一樣。

建立row和col arrays紀錄每個row/col出現多少次B。並且把每個row的array轉成一個string存在row2str裡，方便之後用row index定位到該row的array。 再把整個input 2D grid掃一遍，如果遇到某個grid的同個row/col上有N個B，那就固定那個col index往下掃描不同的row，檢查是否有N個row相等。如果找到相等的情形，把res更新之後要記得把col array歸零避免之後看到又重複計算。

int findBlackPixel(vector<vector<char>>& picture, int N) { // time: O(m * n); space: O(m * n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> row(m, 0), col(n, 0);
    vector<string> row2str(m, "");
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            row2str[i].push_back(picture[i][j]);
            if (picture[i][j] == 'B') {
                ++row[i];
                ++col[j];
            }
        }
    }
    int res = 0, k;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (row[i] == N && col[j] == N) {
                for (k = 0; k < m; ++k) {
                    if (picture[k][j] == 'B') {
                        if (row2str[i] != row2str[k])
                            break;
                    }
                }
                if (k == m) {
                    res += col[j];
                    col[j] = 0; // reset to 0 to avoid dupliacte calculation
                }
            }
        }
    }
    return res;
}

一樣需要先掃描input 2D grid一遍，紀錄每個col index對應到的col有多少B在同個col上。並且用cur同時紀錄B在該row出現的數量，如果該row有N個B，那就把該row的array轉成string，當作unordered_map的key記錄下來。 然後再traverse unordered_map裡的entry，看看是否有string出現N次的，有的話就traverse那個string看看有沒有char是'B'而且該col的B總數為N。找到的話就可以在res上加N。

int findBlackPixel(vector<vector<char>>& picture, int N) { // time: O(m * n); space: O(m * n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> col(n, 0);
    unordered_map<string, int> mp;
    for (int i = 0; i < m; ++i) {
        int cur = 0; // how many 'B's in the current row
        for (int j = 0; j < n; ++j) {
            if (picture[i][j] == 'B') {
                ++col[j];
                ++cur;
            }
        }
        if (cur == N) 
            ++mp[string(picture[i].begin(), picture[i].end())];
    }
    int res = 0;
    for (auto& a : mp) {
        if (a.second != N) continue;
        for (int j = 0; j < n; ++j) {
            if (a.first[j] == 'B' && col[j] == N)
                res += N;
        }
    }
    return res;
}