题解
Medium
用BFS再做了一遍。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
int count = 0;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++) {
if(grid[i][j] == '0' || visited[i][j]) continue;
count++;
visited[i][j] = true;
queue<vector<int>> q;
q.push({i, j});
while(!q.empty()) {
auto t = q.front();
q.pop();
for(int k = 0; k < 4; k++) {
int x = t[0] + dirs[k][0];
int y = t[1] + dirs[k][1];
if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size())
continue;
if(grid[x][y] == '1' && !visited[x][y]) {
visited[x][y] = true;
q.push({x, y});
}
}
}
}
}
return count;
}
};