-
Notifications
You must be signed in to change notification settings - Fork 0
/
200. Number of Islands - BFS.cpp
44 lines (42 loc) · 1.67 KB
/
200. Number of Islands - BFS.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
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
const size_t m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<int> q;
int cnt = 0, r, c;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(visited[i][j]) continue;
visited[i][j] = true;
if(grid[i][j] == '1'){
cnt++;
q.push(i * n + j);
while(!q.empty()){
r = q.front() / n;
c = q.front() % n;
q.pop();
if(r > 0 && grid[r - 1][c] == '1' && !visited[r - 1][c]){
q.push((r - 1) * n + c);
visited[r - 1][c] = true;
}
if(c > 0 && grid[r][c - 1] == '1' && !visited[r][c - 1]){
q.push(r * n + c - 1);
visited[r][c - 1] = true;
}
if(r < m - 1 && grid[r + 1][c] == '1' && !visited[r + 1][c]){
q.push((r + 1) * n + c);
visited[r + 1][c] = true;
}
if(c < n - 1 && grid[r][c + 1] == '1' && !visited[r][c + 1]){
q.push(r * n + c + 1);
visited[r][c + 1] = true;
}
}
}
}
}
return cnt;
}
};