資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中的孤獨畫素 II
假設我們有一張由黑白畫素組成的圖片，我們需要找到在第 R 行和第 C 列中存在的黑色畫素的數量。該數量必須符合以下所有規則：
R 和 C 將恰好包含 N 個黑色畫素。
對於所有在第 C 列具有黑色畫素的行，它們都應該與第 R 行完全相同。
這裡圖片由一個二維字元陣列表示，其中 'B' 和 'W' 分別代表黑色和白色畫素。
如果輸入如下：
| 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，則輸出將為 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），執行：
初始化 j := 0，當 j < m 時，更新（j 加 1），執行：
如果 p[i, j] 等於 'B'，則：
將 j 插入到 r[i] 中
將 i 插入到 c[j] 中
初始化 i := 0，當 i < n 時，更新（i 加 1），執行：
初始化 j := 0，當 j < m 且 i 在 r 中時，更新（j 加 1），執行：
如果 p[i, j] 等於 'B' 且 r[i] 的大小等於 N 且 c[j] 的大小等於 N，則：
ok := true
對於 c[j] 中的每個 x，執行
如果 r[x] 不等於 r[i]，則：
ok := false
退出迴圈
ret := ret + ok
返回 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
82 次檢視
