C++의 외로운 픽셀 II

흑백 픽셀로 구성된 그림이 있다고 가정하고 R행과 C열에 있는 검은색 픽셀의 수를 찾아야 합니다. 이는 다음 모든 규칙과 일치합니다. -

• R과 C는 정확히 N개의 검은색 픽셀을 포함합니다.

• C 열에 검은색 픽셀이 있는 모든 행의 경우 R 행과 정확히 같아야 합니다.

여기에서 그림은 흑백 픽셀 각각에 대해 'B'와 'W'로 구성된 2D 문자 배열로 표시됩니다.

입력이 다음과 같은 경우 -

그리고 N =3이면 출력은 6이 됩니다. 굵은 'B'는 모두 검은색 픽셀이기 때문에 1열과 3열에 있는 'B'입니다. 이제 R =0, C열에서 '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의 열 수

• initialize i :=0의 경우, i

  • j 초기화의 경우:=0, j

    • p[i, j]가 'B'와 같으면 -

      • j를 r[i]에 삽입

      • c[j]에 i 삽입

• initialize i :=0의 경우, i

  • j:=0 초기화의 경우, j

    • p[i, j]가 'B'와 같고 r[i]의 크기가 N과 같고 c[j]의 크기가 N과 같으면 -

      • 확인 :=사실

      • c[j]의 각 x에 대해 수행

        • r[x]가 r[i]와 같지 않으면 -

          • 확인 :=거짓

          • 루프에서 나오세요

      • 렛 :=렛 + 확인

• 리턴 렛

예시(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