Advertisement
vaibhav1906

Number of islands

Jan 4th, 2022
1,027
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     void dfs(vector<vector<char>> &a,vector<vector<int>> &vis,int x,int y)
  4.     {
  5.         int r=a.size();
  6.         int c=a[0].size();
  7.         if(x>=r || x<0 || y>=c || y<0 || vis[x][y]==1 || a[x][y]=='0')
  8.             return;
  9.         vis[x][y]=1;
  10.         dfs(a,vis,x-1,y);
  11.         dfs(a,vis,x,y+1);
  12.         dfs(a,vis,x,y-1);
  13.         dfs(a,vis,x+1,y);
  14.     }
  15.     int numIslands(vector<vector<char>>& a) {
  16.         int r=a.size();
  17.         if(r==0)
  18.             return 0;
  19.         int c=a[0].size();
  20.         if(c==0)
  21.             return 0;
  22.         vector<vector<int>> vis(r,vector<int>(c,0));
  23.         int count=0;
  24.         for(int i=0;i<r;i++)
  25.         {
  26.             for(int j=0;j<c;j++)
  27.             {
  28.                 if(a[i][j]=='1' && vis[i][j]==0)
  29.                 {
  30.                     dfs(a,vis,i,j);
  31.                     count++;
  32.                 }
  33.             }
  34.         }
  35.         return count;
  36.     }
  37. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement