来源:Leetcode, Google常考题
原帖:https://leetcode.com/problems/number-of-islands/
题目:
Given a 2d grid map of '1's (land) and '0's (water), count 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.
思路:找到连通域的数目,典型的bfs, dfs题目。
代码:DFS
原帖:https://leetcode.com/problems/number-of-islands/
题目:
Given a 2d grid map of '1's (land) and '0's (water), count 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.
思路:找到连通域的数目,典型的bfs, dfs题目。
代码:DFS
class Solution {
public:
vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};
void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int r, int c) {
int M = grid.size(), N = grid[0].size();
visited[r][c] = true;
for (auto o : offset) {
int i = r + o.first, j = c + o.second;
if (i < 0 || i >= M || j < 0 || j >= N) continue;
if (grid[i][j] == '0' || visited[i][j]) continue;
dfs(grid, visited, i, j);
}
}
int numIslands(vector<vector<char>> &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int M = grid.size(), N = grid[0].size();
vector<vector<bool>> visited(M,vector<bool>(N,false));
int count = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1' && !visited[i][j]) {
count++;
dfs(grid, visited, i,j);
}
}
}
return count;
}
};
代码:BFS
class Solution {
public:
vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};
int numIslands(vector<vector<char>> &grid) {
if (grid.empty() || grid[0].empty()) return 0;
int M = grid.size(), N = grid[0].size();
vector<vector<bool>> visited(M,vector<bool>(N,false));
int count = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1' && !visited[i][j]) {
count++;
queue<pair<int,int>> q;
visited[i][j] = true;
q.push({i,j});
while (!q.empty()) {
auto neigh = q.front(); q.pop();
for (auto o : offset) {
int r = neigh.first + o.first, c = neigh.second + o.second;
if (r < 0 || r >= M || c < 0 || c >= N) continue;
if (visited[r][c] || grid[r][c] == '0') continue;
visited[r][c] = true;
q.push({r,c});
}
}
}
}
}
return count;
}
};
No comments:
Post a Comment