-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathLeetCode_200_40.cpp
More file actions
86 lines (73 loc) · 2.41 KB
/
LeetCode_200_40.cpp
File metadata and controls
86 lines (73 loc) · 2.41 KB
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
* @lc app=leetcode id=200 lang=cpp
*
* [200] Number of Islands
*/
/*
class Solution {
public:
int numIslands(const vector<vector<char>>& inputGrid) const {
vector<vector<char>> grid = inputGrid;
const int rows = grid.size();
const int cols = rows ? grid[0].size() : 0;
int islandCount = 0;
stack<pair<int, int>> s;
for (int j = 0; j < rows; j++) {
for (int k = 0; k < cols; k++) {
if (grid[j][k] == '1') {
islandCount++;
grid[j][k] = '0';
s.push({j, k});
while (!s.empty()) {
int m = s.top().first;
int n = s.top().second;
if (n + 1 < cols && grid[m][n + 1] == '1') {
grid[m][n + 1] = '0';
s.push({m, n + 1});
} else if (m + 1 < rows && grid[m + 1][n] == '1') {
grid[m + 1][n] = '0';
s.push({m + 1, n});
} else if (n - 1 >= 0 && grid[m][n - 1] == '1') {
grid[m][n - 1] = '0';
s.push({m, n - 1});
} else if (m - 1 >= 0 && grid[m - 1][n] == '1') {
grid[m - 1][n] = '0';
s.push({m - 1, n});
} else {
s.pop();
}
}
}
}
}
return islandCount;
}
};
*/
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int numTotal=0;
for(int i=0; i<grid.size(); ++i) {
for(int j=0; j<grid[i].size(); ++j) {
if(grid[i][j]=='1') {
++numTotal;
FloodFillIsland(grid,i,j);
}
}
}
return numTotal;
}
void FloodFillIsland(vector<vector<char>>& grid, int x, int y){
if(x<0 || x>=grid.size() ||
y < 0 || y >= grid[0].size())
return;
if(grid[x][y] != '1')
return;
grid[x][y]='0';
FloodFillIsland(grid,x-1,y);
FloodFillIsland(grid,x+1,y);
FloodFillIsland(grid,x,y-1);
FloodFillIsland(grid,x,y+1);
}
};