首页 > 其他 > 详细

[LeetCode]Number of Islands

时间:2015-04-08 21:07:16      阅读:324      评论:0      收藏:0      [点我收藏+]

原题链接:https://leetcode.com/problems/number-of-islands/

题意描述:

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 public class Solution {
 2     public static boolean flag = false;
 3 
 4     public int numIslands(char[][] grid) {
 5         boolean[][] visited = new boolean[grid.length][];
 6         for (int i = 0; i < grid.length; i++)
 7             visited[i] = new boolean[grid[i].length];
 8         for (int i = 0; i < grid.length; i++) {
 9             for (int j = 0; j < grid[0].length; j++) {
10                 visited[i][j] = false;
11             }
12         }
13         int res = 0;
14         for (int i = 0; i < grid.length; i++) {
15             for (int j = 0; j < grid[0].length; j++) {
16                 flag = false;
17                 process(i, j, grid, visited);
18                 if (flag)
19                     res++;
20             }
21         }
22         return res;
23     }
24 
25     public void process(int i, int j, char[][] grid, boolean[][] visited) {
26         if (grid[i][j] != ‘1‘ || visited[i][j])
27             return;
28         visited[i][j] = true;
29         flag = true;
30         if (j >= 1)
31             process(i, j - 1, grid, visited);
32         if (i >= 1)
33             process(i - 1, j, grid, visited);
34         if(i+1<grid.length)
35             process(i + 1, j, grid, visited);
36         if(j+1<grid[0].length)
37             process(i, j + 1, grid, visited);
38     }
39 }

 

[LeetCode]Number of Islands

原文:http://www.cnblogs.com/codershell/p/4403489.html

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