C ++中的孤独像素II
假设我们有一个由黑白像素组成的图片,我们必须找到存在于R行和C列的黑色像素的数量。这符合以下所有规则-
R和C将恰好包含N个黑色像素
对于在C列具有黑色像素的所有行,它们应与R列完全相同。
在此,图片由2D字符数组表示,该数组分别由“B”和“W”组成,分别用于黑色和白色像素。
如果输入像-
并且N=3,则输出将为6。因为所有粗体“B”都是黑色像素,因此在第1列和第3列都是“B”。现在,如果我们在行R=0和列C=1处采用“B”因此,举一个例子:规则1,R=0行和C=1列都具有N个'B'像素。以及规则2,在C列=1的行具有'B'像素,分别是第0行,第1行和第2行。它们与R=0行完全相同。
为了解决这个问题,我们将遵循以下步骤-
ret:=0
定义一个映射r另一个映射c
n:=p的行数,m:=p的列数
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
如果p[i,j]与'B'相同,则-
将j插入r[i]
将我插入c[j]
对于初始化j:=0,当j<m时,更新(将j增加1),执行-
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
如果p[i,j]与'B'相同,并且r[i]的大小与N相同,而c[j]的大小与N相同,则-
如果r[x]不等于r[i],则-
好的:=假
从循环中出来
好的:=真
对于c[j]中的每个x,
ret:=ret+确定
对于初始化j:=0,当j<m并且i在r中时,更新(将j增加1),-
返回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