C++의 고유 섬 수

이진 2D 어레이 그리드가 있다고 가정합니다. 여기에서 섬은 4방향(수평 또는 수직)으로 연결된 1(랜드) 그룹입니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다. 우리는 별개의 섬의 수를 세어야 합니다.

한 섬이 다른 섬과 동일하게 변환될 수 있고(회전하거나 반사되지 않음) 섬은 다른 섬과 동일한 것으로 간주됩니다.

따라서 입력이 다음과 같으면

그러면 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dfs() 함수를 정의하면 x, y, grid, temp, c,

  가 필요합니다.

• 그리드 행과 열 내부에 x와 y가 없고 grid[x,y]가 0이면 -

  • 반환

• 그리드[x, y] :=0

• temp :=임시 연결 c

• dfs(x + 1, y, 그리드, 온도, 'r')

• dfs(x - 1, y, 그리드, 온도, 'l')

• dfs(x, y + 1, 그리드, 온도, 'd')

• dfs(x, y - 1, 그리드, 온도, 'u')

• temp :=임시 'b' 연결

• 주요 방법에서 다음을 수행하십시오 -

• ret :=0

• 방문한 한 세트 정의

• for initialize i :=0, i <그리드의 행 개수, 업데이트(i 1만큼 증가), 수행 -

  • j 초기화의 경우:=0, j <그리드의 열 개수일 ​​때 업데이트(j를 1만큼 증가), 수행 -

    • grid[i, j]가 0이 아니면 -

      • aux :=빈 문자열

      • dfs(i, j, 그리드, 보조, 's')

      • aux가 방문되지 않은 경우 -

        • (ret 1 증가)

        • 방문에 aux 삽입

• 리턴 렛

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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