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
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
分析：
这是网上流传最广的深度优先解法，确实漂亮，通俗易理解。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int result=0;
if(grid.empty() || grid[0].empty())
return result;
int rows=grid.size();
int cols=grid[0].size();
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(grid[i][j]=='1')//如果是岛屿
{
dfs(grid,i,j,rows,cols);//深搜，将该位置(i,j)四周的1都置0
result++;
}
}
}
return result;
}
void dfs(vector<vector<char>>& grid,int i,int j,int rows,int cols)
{
grid[i][j]='0';
if(i > 0 && grid[i-1][j] == '1')//上边置0
dfs(grid,i-1,j,rows,cols);
if(i < rows-1 && grid[i+1][j] == '1')//下边同理
dfs(grid,i+1,j,rows,cols);
if(j > 0 && grid[i][j-1] == '1')//左边
dfs(grid,i,j-1,rows,cols);
if(j < cols-1 && grid[i][j+1] == '1')//右边
dfs(grid,i,j+1,rows,cols);
}
};注：本博文为EbowTang原创，后续可能继续更新本文。如果转载，请务必复制本条信息！
原文地址：http://blog.csdn.net/ebowtang/article/details/51636977
原作者博客：http://blog.csdn.net/ebowtang
本博客LeetCode题解索引：http://blog.csdn.net/ebowtang/article/details/50668895
<LeetCode OJ> 200. Number of Islands
原文：http://blog.csdn.net/ebowtang/article/details/51636977