C++のLonelyPixelII

黒と白のピクセルで構成される画像があるとすると、行Rと列Cに存在する黒のピクセルの数を見つける必要があります。これは次のすべてのルールに沿っています-

• RとCには正確にN個の黒いピクセルが含まれます

• 列Cに黒いピクセルがあるすべての行について、行Rとまったく同じである必要があります。

ここで、画像は、それぞれ黒と白のピクセルの「B」と「W」で構成される2D文字配列で表されます。

入力が-

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

• あるマップまたは別のマップを定義するc

• n：=pの行数、m：=pの列数

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • p [i、j]が'B'と同じ場合、-

      • jをr[i]

        に挿入します

      • iをc[j]

        に挿入します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • 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