C++での個別の島IIの数

グリッドと呼ばれる空でない2Dバイナリ配列があるとします。ここで、島は4方向に接続された1（土地を表す）のグループです。グリッドの4つのエッジすべてが水に囲まれていると想定することもできます。

異なる島の数を数える必要があります。島が同じ形状であるか、90度、180度、または270度の回転のみ、または左右方向または上下方向の反射後の同じ形状である場合、島は別の島と同じであると見なされます。

したがって、入力が次のような場合、

その場合、出力は1になります

これを解決するには、次の手順に従います-

• 1つのマップを定義するm

• 関数dfs（）を定義します。これには、i、j、grid、idx、

  が必要です。

• iとjがグリッドの範囲内にあり、grid [i、j]が0の場合、-

  • 戻る

• grid [i、j]：=0

• m [idx]

  の最後に{i、j}を挿入します

• dfs（i + 1、j、grid、idx）

• dfs（i-1、j、grid、idx）

• dfs（i、j-1、grid、idx）

• dfs（i、j + 1、grid、idx）

• 1つの関数norm（）を定義します。これには、配列v

  が必要です。

  • 8行のペアの2D配列を1つ定義します

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

    • x：=v [i] .first

    • y：=v [i] .second

    • s [0]

      の最後に{x、y}を挿入します

    • s [1]

      の最後に{x、-y}を挿入します

    • s [2]

      の最後に{--x、y}を挿入します

    • s [3]

      の最後に{--x、-y}を挿入します

    • s [4]

      の最後に{y、x}を挿入します

    • s [5]

      の最後に{y、-x}を挿入します

    • s [6]

      の最後に{--y、x}を挿入します

    • s [7]

      の最後に{--y、-x}を挿入します

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

    • 配列を並べ替えるs[i]

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

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

      • s [i、j] .first：=s [i、j] .first --s [i、0] .first

      • s [i、j] .second：=s [i、j] .second --s [i、0] .second

    • s [i、0] .first：=0

    • s [i、0] .second：=0

  • 配列を並べ替える

  • s [0]

    を返します

• メインの方法から、次のようにします-

• 1セットのポイントを定義する

• cnt：=1

• 初期化i：=0の場合、i <グリッドのサイズの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <グリッド[0]のサイズの場合、更新（jを1増やします）、＆miuns;

    を実行します。

    • grid [i、j]が1と同じ場合、-

      • （cntを1増やします）

      • dfs（i、j、grid、cnt）

      • norm（m [cnt]）をptsに挿入します

• ptsの戻りサイズ

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map < int, vector < pair <int, int> > > m;
   void dfs(int i, int j, vector < vector <int> >& grid, int idx){
      if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j])
         return;
      grid[i][j] = 0;
      m[idx].push_back({ i, j });
      dfs(i + 1, j, grid, idx);
      dfs(i - 1, j, grid, idx);
      dfs(i, j - 1, grid, idx);
      dfs(i, j + 1, grid, idx);
   }
   vector < pair <int, int> > norm(vector < pair < int, int > > v){
      vector<vector<pair<int, int> > > s(8);
      for (int i = 0; i < v.size(); i++) {
         int x = v[i].first;
         int y = v[i].second;
         s[0].push_back({ x, y });
         s[1].push_back({ x, -y });
         s[2].push_back({ -x, y });
         s[3].push_back({ -x, -y });
         s[4].push_back({ y, x });
         s[5].push_back({ y, -x });
         s[6].push_back({ -y, x });
         s[7].push_back({ -y, -x });
      }
      for (int i = 0; i < s.size(); i++) {
         sort(s[i].begin(), s[i].end());
      }
      for (int i = 0; i < s.size(); i++) {
         for (int j = 1; j < v.size(); j++) {
            s[i][j].first = s[i][j].first - s[i][0].first;
            s[i][j].second = s[i][j].second - s[i][0].second;
         }
         s[i][0].first = 0;
         s[i][0].second = 0;
      }
      sort(s.begin(), s.end());
      return s[0];
   }
   int numDistinctIslands2(vector<vector<int>>& grid) {
      set<vector<pair<int, int> > > pts;
      int cnt = 1;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
               cnt++;
               dfs(i, j, grid, cnt);
               pts.insert(norm(m[cnt]));
            }
         }
      }
      return pts.size();
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}};
   cout << (ob.numDistinctIslands2(v));
}

入力

{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}

出力

1