Số quần đảo đã đóng trong C ++

Giả sử chúng ta có một lưới 2D bao gồm 0s (đất) và 1s (dưới nước). Đảo là một nhóm các số 0 được kết nối có hướng 4 cực đại. Một hòn đảo đóng là một hòn đảo được bao quanh hoàn toàn bởi 1s. Chúng ta phải tìm số lượng các hòn đảo đã đóng cửa. Vì vậy, nếu lưới giống như

Vì vậy, đầu ra sẽ là 2. Có hai hòn đảo, được bao quanh hoàn toàn bởi nước.

Để 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 cờ biến

• Xác định một phương thức gọi là dfs, phương thức này sẽ lấy lưới, i, j, n và m

• nếu tôi và j không nằm trong phạm vi của lưới, thì hãy đặt cờ:=false và return

• nếu g [i, j] =1 hoặc g [i, j] =-1 thì trả về

• nếu g [i, j] =0 thì g [i, j] =-1

• gọi dfs (g, i + 1, j, n, m), dfs (g, i, j + 1, n, m), dfs (g, i - 1, j, n, m), dfs (g, i, j-1, n, m)

• Phương thức chính sẽ giống như -

• tạo ma trận dp có thứ tự n x m và điền nó bằng -1

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi 0 đến m - 1

    • nếu g [i, j] =0 thì

      • cờ:=true

      • dfs (g, i, j, n, m)

      • cờ:=true

      • ans:=ans + cờ

• trả lại ans

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector < vector <int> > dp;
   bool flag;
   void dfs(vector<vector<int>>& g, int i, int j, int n, int m){
      if(i>=n || j >=m || i<0 || j<0){
         flag = false;
         return ;
      }
      if(g[i][j] == 1 || g[i][j] == -1)return;
      if(g[i][j] == 0)g[i][j] = -1;
      dfs(g, i+1, j, n, m);
      dfs(g, i, j+1, n, m);
      dfs(g, i-1, j, n, m);
      dfs(g,i, j-1, n, m);
   }
   int closedIsland(vector<vector<int>>& g) {
      int ans = 0;
      int n = g.size();
      int m = g[0].size();
      dp = vector < vector <int> > (n, vector <int> (m, -1));
      for(int i = 0; i < n ; i++){
         for(int j = 0; j < m; j++){
            if(g[i][j] == 0){
               flag = true;
               dfs(g, i , j ,n ,m);
               ans += flag;
            }
         }
      }
   return ans;
   }
};
main(){
   vector<vector<int>> v =
   {{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0
   ,1},{1,1,1,1,1,1,1,0}};
   Solution ob;
   cout << (ob.closedIsland(v));
}

Đầu vào

[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

Đầu ra

2