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.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
思路：与Surrounded Regions（middle）☆的思路是一样的，也可以用广度和深度优先搜索。当遇到1的时候，把区域数加1，并把与这个1相连的整片区域标记为2.
下面的BFS用时25ms，DFS用时16ms
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return ;
int num = ;
for(int i = ; i < grid.size(); ++i)
for(int j = ; j < grid[].size(); ++j)
if(grid[i][j] == '')
{
num++;
BFS(grid, i, j);
}
return num;
}
void BFS(vector<vector<char>>& grid, int r, int c)
{
queue<pair<int, int>> q;
q.push(make_pair(r, c));
while(!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
if(i >= && j >= && i < grid.size() && j < grid[].size() && grid[i][j] == '')
{
grid[i][j] = ;
q.push(make_pair(i - , j));
q.push(make_pair(i + , j));
q.push(make_pair(i, j - ));
q.push(make_pair(i, j + ));
}
}
}
void DFS(vector<vector<char>>& grid, int r, int c)
{
if(r >= && c >= && r < grid.size() && c < grid[].size() && grid[r][c] == '')
{
grid[r][c] = ;
DFS(grid, r - , c);
DFS(grid, r + , c);
DFS(grid, r, c - );
DFS(grid, r, c + );
}
}
很奇怪的是，开始我写的时候BFS多传了一个变量就TLE了？？为什么呢？？
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return ;
int num = ;
for(int i = ; i < grid.size(); ++i)
{
for(int j = ; j < grid[].size(); ++j)
{
if(grid[i][j] == '')
BFS(grid, i, j, num);
}
}
return num;
}
void BFS(vector<vector<char>>& grid, int r, int c, int &num)
{
num++;
queue<pair<int, int>> q;
q.push(make_pair(r, c));
while(!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
if(i >= && j >= && i < grid.size() && j < grid[].size() && grid[i][j] == '')
{
grid[i][j] = num + ;
q.push(make_pair(i - , j));
q.push(make_pair(i + , j));
q.push(make_pair(i, j - ));
q.push(make_pair(i, j + ));
}
}
}