Lonely Pixel II trong C ++

Giả sử chúng ta có một bức ảnh bao gồm các pixel đen và trắng, chúng ta phải tìm số pixel đen có ở hàng R và cột C. Điều đó phù hợp với tất cả các quy tắc sau -

R và C sẽ chứa chính xác N pixel đen
Đối với tất cả các hàng có pixel màu đen ở cột C, chúng phải giống hệt như hàng R.

Ở đây, hình ảnh được thể hiện bằng một mảng ký tự 2D bao gồm 'B' và 'W', tương ứng cho các pixel đen và trắng.

Nếu đầu vào giống như -

W	B	W	B	B	W
W	B	W	B	B	W
W	B	W	B	B	W
W	W	B	W	B	W

Và N =3, thì đầu ra sẽ là 6. Bởi vì tất cả các chữ "B" in đậm là các điểm ảnh màu đen, tất cả các chữ "B ở cột 1 và 3. Bây giờ nếu chúng ta lấy" B "ở hàng R =0 và cột C =1 vì vậy, ví dụ:Quy tắc 1, hàng R =0 và cột C =1 đều có chính xác N 'B' pixel. và Quy tắc 2, các hàng có pixel ‘B’ tại cột C =1 là hàng 0, hàng 1 và hàng 2. Chúng hoàn toàn giống với hàng R =0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=0
Xác định một bản đồ r một bản đồ khác c
n:=số hàng của p, m:=số cột của p
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - nếu p [i, j] giống với 'B' thì -
    - chèn j vào r [i]
    - chèn tôi vào c [j]
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - nếu p [i, j] giống với 'B' và kích thước của r [i] giống với N và kích thước của c [j] giống với N, thì -
    - ok:=true
    - đối với mỗi x trong c [j], thực hiện
      - nếu r [x] không bằng r [i] thì -
        
        ok:=false
        
        Ra khỏi vòng lặp
    - ret:=ret + ok
trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{{'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

Lonely Pixel II trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra