533. Lonely Pixel II

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/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:

  • Row R and column C both contain exactly N black pixels.
  • 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:

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

cpp


my code:

  1. 审题很重要,第2个条件是完全相同,我最初理解为B的个数相同,所以出现错误。

  2. for循环后的值为n,而不是n-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
int findBlackPixel(vector<vector<char>>& picture, int N) {
if(picture.size()==0) return 0;
if(picture[0].size()==0) return 0;
int m = picture.size();
int n = picture[0].size();
vector<int> dp1(m, 0);
vector<int> dp2(n, 0);
for(int i=0; i<m; i++){
int tmp = 0;
for(int j=0; j<n; j++){
if(picture[i][j]=='B')
tmp++;
}
dp1[i] = tmp;
}

for(int i=0; i<n; i++){
int tmp = 0;
for(int j=0; j<m; j++){
if(picture[j][i]=='B')
tmp++;
}
dp2[i] = tmp;
}

int res = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(dp1[i]==dp2[j] && dp1[i]==N){
int k;
int flag = true;
for(k=0; k<m; k++){
if(picture[k][j]=='B')
for(int l=0; l<n; l++){
if(picture[i][l]!=picture[k][l]){
flag = false;
break;
}
}
}
if(flag == true)
res++;
}
}
}

return res;
}
};
谢谢你,可爱的朋友。