Number of Closed Islands in C++

Suppose we have a 2D grid consists of 0s (as land) and 1s (as water). An island is a maximal 4- directionally connected group of 0s. A closed island is an island totally surrounded by 1s. We have to find the number of closed islands. So if the grid is like

So the output will be 2. There are two islands, that are completely surrounded by water.

To solve this, we will follow these steps −

• Define a variable flag

• Define a method called dfs, this will take the grid, i, j, n and m

• if i and j are not inside the range of the grid, then set flag := false and return

• if g[i,j] = 1 or g[i, j] = -1, then return

• if g[i, j] = 0, then g[i, j] = -1

• call 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)

• The main method will be like −

• create a dp matrix of order n x m, and fill it with -1

• for i in range 0 to n – 1

  • for j in range 0 to m – 1

    • if g[i, j] = 0, then

      • flag := true

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

      • flag := true

      • ans := ans + flag

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

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

Input

[[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]]

Output

2