Breadth-first Search - Example
Leetcode 200 Number of Islands
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.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
Analysis:
The BFS method is straightforward: once we find a position with value of '1', then we can start the layer-by-layer expansion. To avoid redundant scan, we need to label the positions visited. Once the search is done, the count of island is updated by adding one.
For the four direction expansion, a trick is used in the for loop, to short the code.
See the code below:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if(!grid.size() || !grid.front().size()) return 0;
int res=0, m=grid.size(), n=grid.front().size();
vector<vector<int>> vis(m, vector<int>(n, 0));
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
if(grid[i][j] == '1' && !vis[i][j]){
res++;
bfs(grid, vis, i, j);
}
}
}
return res;
}
private:
void bfs(vector<vector<char>>& g, vector<vector<int>>& v, int a, int b){
vector<int> dirs = {-1, 0, 1, 0, -1};
queue<pair<int, int>> q;
q.push({a, b});
v[a][b] = 1;
while(q.size()) {
auto t = q.front();
q.pop();
for(int i=0; i+1<dirs.size(); ++i) {
int x = dirs[i] + t.first, y = dirs[i+1] + t.second;
if(x<0 || x>=g.size() || y<0 || y>=g.front().size() || g[x][y] == '0' || v[x][y]) continue;
q.push({x, y});
v[x][y] = 1;
}
}
}
};
Comments
Post a Comment