<LeetCode OJ> 200. Number of Islands
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了<LeetCode OJ> 200. Number of Islands，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1733字，纯文字阅读大概需要3分钟。
内容图文
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
200. Number of Islands' ref='nofollow'>
原文：http://blog.csdn.net/ebowtang/article/details/51636977
内容总结
以上是互联网集市为您收集整理的<LeetCode OJ> 200. Number of Islands全部内容，希望文章能够帮你解决<LeetCode OJ> 200. Number of Islands所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。