注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex200 Number of Islands  

2015-05-23 22:16:00|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

这道题目第一眼看,觉得和图有点儿关系,所以感觉有点儿难,没什么思路。就是想着把所有的连通的1遍历一遍,最后全部置为0.后来看了网上的思路,用的深度递归,也可以用宽度优先递归。下面的有一个题目就恶心了,深度递归死活都过不去,runtime error。
这一题,最关键的是连通的区域遍历的时候一定要先置为0,否则就是循环了,每次递归需要扩展四个方向。

/*
* 以前没做过这样的题,不过感觉上可以用深度遍历来做
* 参考网上的确实这种解法,每次遍历过后就把经过的点抹掉
*/
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size()<=0 || grid[0].size()<=0)
return 0;
int m = grid.size();
int n = grid[0].size();
int count = 0; //用来计数的
int i, j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (grid[i][j] == '1')
{
traverse(grid,i,j);
count++;
}
}
}
return count;
}
void traverse(vector<vector<char>>& grid,int x,int y)
{
if (x >= 0 && y >= 0 && x < grid.size()&& y < grid[0].size()&&grid[x][y]=='1')
{
grid[x][y] = '0';
traverse(grid, x - 1, y); //left
traverse(grid, x + 1, y); //right
traverse(grid, x, y-1); // up
traverse(grid, x, y+1); //down
}
}
};


参考
http://www.cnblogs.com/easonliu/p/4402077.html
  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017