首页 > 其他 > 详细

Number of islands

时间:2015-04-19 06:27:03      阅读:226      评论:0      收藏:0      [点我收藏+]

题目:

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

 

思路:In this problem, we will use a algorithm called "Flood Fill".

Here is a link about flood fill: http://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

So, our idea is, when we found a ‘1‘, we increase count by 1 and mark all adjacent ‘1‘s as ‘2‘. Then we keep searching next ‘1‘.

Code:

 1 public int numIslands(char[][] grid) {
 2         if (grid == null || grid.length == 0 || grid[0].length == 0) {
 3             return 0;
 4         }
 5         int count = 0;
 6         for (int i = 0; i < grid.length; i++) {
 7             for (int j = 0; j < grid[0].length; j++) {
 8                 if (grid[i][j] == ‘1‘) {
 9                     count++;
10                     floodfill(i, j, grid);
11                 }else{
12                     continue;
13                 }
14             }
15         }
16         return count;
17     }
18     
19     private static void floodfill(int x, int y, char[][] grid) {
20         if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
21             return;
22         }
23         if (grid[x][y] != ‘1‘) {
24             return;
25         }
26         grid[x][y] = ‘2‘;
27         floodfill(x + 1, y, grid);
28         floodfill(x - 1, y, grid);
29         floodfill(x, y + 1, grid);
30         floodfill(x, y - 1, grid);
31     }

这个算法很简单明了,记下就好。但代码还可以优化。现在308ms。

Number of islands

原文:http://www.cnblogs.com/gonuts/p/4438594.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!