[LeetCode] 533. Lonely Pixel II

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/lonely-pixel-ii/

Solution:
First step need to scan the 2D matrix to figure out how many columns and rows having the N 'B'. And we can record the index into two vectors: one for the row collections; and the other for the column collection. Then for each column inside the column collection, we need to check the validity by going though the associated row to the 'B' element inside the column. If there's no same row existing in the previously row collection with N 'B', just go to the next column; if yes, we need to further check all the associated rows to the rest 'B' elements inside the same column. If all of them (associated rows) are the same, count +1; or, go to the next column. Finally, return count * N.

An alternative way is that when counting the columns, after knowing there's N 'B' elements, we can further make sure all the associated rows to the 'B' element inside the column are the same. If not, it is not necessary to keep it in the column collection. Then in the following step, we just need to make sure there's at least one row existing in the row collections matches the associated row to the 'B' element inside the column to be checked.

Code:

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        if(picture.empty() || picture.front().empty()) return 0;
        int res = 0;
        int m = picture.size(), n = picture.front().size();
        vector<int> v1, v2;
        for(int i=0; i<m; ++i){
            int t = 0;
            for(int j=0; j<n; ++j){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v1.push_back(i);
        }
        for(int j=0; j<n; ++j){
            int t = 0;
            for(int i=0; i<m; ++i){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v2.push_back(j);
        }
        for(int j=0; j<v2.size(); ++j){
            for(int i=0; i<m; ++i){
                if(picture[i][v2[j]] !='B') continue;
                if(picture[i][v2[j]]=='B'&&isV(picture, i, v1)){
                    vector<int> v3(1, i);
                    bool flag = true;
                    for(int k=0; k<m; ++k){
                        if(picture[k][v2[j]]=='B'&&!(isV(picture, k, v3))){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) ++res;
                }
                break;
            }
        }
        return res*N;
    }
private:
bool isV(vector<vector<char>> &p, int x, vector<int> &v1){
        for(int i=0; i<v1.size(); ++i){
            bool flag = true;
            for(int j=0; j<p.front().size(); ++j){
                if(p[v1[i]][j] != p[x][j]){
                    flag = false;
                    break;
                }
            }
            if(flag) return true;
        }
        return false;
    }
};