-
Notifications
You must be signed in to change notification settings - Fork 0
/
numberOfIand.cpp
65 lines (55 loc) · 1.5 KB
/
numberOfIand.cpp
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
200. Number of Islands
Medium
18.5K
410
Companies
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"], // 1,1,1,1
["1","1","0","1","0"],// 1,1
["1","1","0","0","0"],// 1,1 all connected to each others
["0","0","0","0","0"]
]
Output: 1 // so
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
class Solution {
public:
// Note :
/* 2 condition
1. if meet '1' then findout the adjucent of all '1' .
2. then make '0' instead of '1'.
*/
void dfs(vector<vector<char>>&grid,int i,int j){
if(i>grid.size()-1 || j>grid[0].size()-1|| i<0 ||j<0 || grid[i][j]!='1'){
return ;
}
grid[i][j]='0';
dfs(grid,i+1,j); // right
dfs(grid,i,j+1); // left
dfs(grid,i,j-1); // up
dfs(grid,i-1,j); // down
}
int numIslands(vector<vector<char>>& grid) {
int n=grid.size();
int m=grid[0].size();
int count=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='1'){
dfs(grid,i,j);
count++;
}
}
}
return count;
}
};