Số quần đảo khác biệt trong C ++

Giả sử chúng ta có một lưới mảng 2D nhị phân, ở đây một hòn đảo là một nhóm của 1 (đất) được kết nối 4 theo hướng (ngang hoặc dọc.) Chúng ta có thể giả sử cả bốn cạnh của lưới đều được bao quanh bởi nước. Chúng tôi phải đếm số lượng các hòn đảo riêng biệt.

Một hòn đảo được coi là giống với hòn đảo khác khi một hòn đảo có thể được dịch chuyển (và không xoay hoặc phản chiếu) để cân bằng với hòn đảo kia.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm dfs (), hàm này sẽ lấy x, y, lưới, tạm thời, c,

• nếu x và y không nằm trong các hàng và cột của lưới và lưới [x, y] là 0 thì -

  • trở lại

• lưới [x, y]:=0

• temp:=temp nối c

• dfs (x + 1, y, lưới, nhiệt độ, 'r')

• dfs (x - 1, y, grid, temp, 'l')

• dfs (x, y + 1, lưới, nhiệt độ, 'd')

• dfs (x, y - 1, grid, temp, 'u')

• temp:=temp concatenate 'b'

• Từ phương thức chính, hãy làm như sau -

• ret:=0

• Xác định một tập hợp đã truy cập

• để khởi tạo i:=0, khi tôi

  • để khởi tạo j:=0, khi j

    • nếu lưới [i, j] khác 0, thì -

      • aux:=chuỗi trống

      • dfs (i, j, grid, aux, 's')

      • nếu aux không được truy cập, thì -

        • (tăng ret lên 1)

        • chèn aux vào đã thăm

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

3