-
Notifications
You must be signed in to change notification settings - Fork 0
/
Number-of-Islands
35 lines (28 loc) · 1.12 KB
/
Number-of-Islands
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Refrence - https://leetcode.com/problems/number-of-islands/
-------------------------------------------------------------------------------------------------
class Solution {
public:
void dfs(char node , vector<vector<bool>>& vis, vector<vector<char>>&grid , int i , int j ){
if( i < 0 or j < 0 or i==grid.size() or j == grid[0].size() or grid[i][j] == '0' or vis[i][j] )return;
vis[i][j] = true;
dfs(node , vis , grid , i , j + 1 );
dfs(node , vis , grid , i + 1, j );
dfs(node , vis , grid , i , j - 1 );
dfs(node , vis , grid , i- 1, j );
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> vis(n , vector<bool>(m , false));
int ans = 0;
for(int i=0 ;i<n ;i++){
for(int j=0 ;j<m ;j++){
if(grid[i][j] == '1' and !vis[i][j]){
ans++; // island++
dfs(grid[i][j] , vis , grid , i , j );
}
}
}
return ans;
}
};