C++の個別の島の数

バイナリ2D配列グリッドがあるとします。ここで、島は4方向（水平または垂直）に接続された1（土地）のグループです。グリッドの4つのエッジすべてが水に囲まれていると想定できます。個別の島の数を数える必要があります。

ある島が他の島と等しくなるように変換できる（回転または反射されていない）場合、島は別の島と同じであると見なされます。

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

その場合、出力は3

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

• 関数dfs（）を定義します。これには、x、y、grid、temp、c、

  が必要です。

• xとyがグリッドの行と列の内側になく、grid [x、y]が0の場合、-

  • 戻る

• grid [x、y]：=0

• temp：=temp concatenate c

• dfs（x + 1、y、grid、temp、'r'）

• dfs（x-1、y、grid、temp、'l'）

• dfs（x、y + 1、grid、temp、'd'）

• dfs（x、y-1、grid、temp、'u'）

• temp：=temp concatenate'b'

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

• ret：=0

• 訪問した1セットを定義する

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

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

    • grid [i、j]がゼロ以外の場合、-

      • aux：=空の文字列

      • dfs（i、j、grid、aux、's'）

      • auxが訪問されていない場合、-

        • （retを1増やします）

        • 訪問済みにAuxを挿入

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   void dfs(int x, int y, vector < vector <int> >& grid, string& temp, char c){
      if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y])
         return;
      grid[x][y] = 0;
      temp += c;
      dfs(x + 1, y, grid, temp, 'r');
      dfs(x - 1, y, grid, temp, 'l');
      dfs(x, y + 1, grid, temp, 'd');
      dfs(x, y - 1, grid, temp, 'u');
      temp += 'b';
   }
   int numDistinctIslands(vector<vector<int>>& grid) {
      int ret = 0;
      set<string> visited;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j]) {
               string aux = "";
               dfs(i, j, grid, aux, 's');
               if (!visited.count(aux)) {
                  ret++;
                  visited.insert(aux);
               }
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v =
   {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
   cout<<(ob.numDistinctIslands(v));
}

入力

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

出力

3