LeetCode(Trees&Graphs)Numbers of Islands

2018-06-24

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

　　思路：一开始觉得非常难，后来看了很多人的解法，发现用DFS或者是BFS的居多，DFS即深度优先搜索，BFS即广度优先搜索。这两种遍历方法是图的遍历中最常用的，之前只是知道这种算法的思想，没有将之代码化过，正好拿这个问题练练手，看了一个大神的代码后发现甚是优雅，而且特别容易读懂，也让我对深度优先搜索有了更加深入的理解，其实本问题最主要的就是找到“1”,如果1有多个相邻的就一直找，直到找不到为止，将这些全部在一起的”1”看做是一个岛，然后找到了就做标记“x”，再从标记点出发从四个方向：上下左右去找下一个是“1”的点，找到了就继续深入去找，找不到就返回当前标记的结点。代码如下：

class Solution {
    //(dx[d],dy[d])represent directions which the current position can go to next.
    //(0,-1)-->up,(0,1)-->down,(-1,0)-->left,(1,0)-->right
    int [] dx={0,0,-1,1};
    int [] dy={-1,1,0,0};
    public int numIslands(char[][] grid) {
        if(grid.length==0 || grid==null){
            return 0;
        }
        int xlen=grid.length;
        int ylen=grid[0].length;
        int count=0;
        
        for(int i=0;i<xlen;i++){
            for(int j=0;j<ylen;j++){
                if(grid[i][j]=='1'){
                    explore(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    public void explore(char [][] grid, int i, int j){
        grid[i][j]='x';
        int xlen=grid.length;
        int ylen=grid[0].length;
        int dlen=dx.length;
        for(int d=0;d<dlen;d++){
            if(i+dy[d]<xlen && i+dy[d]>=0 && j+dx[d]<ylen && j+dx[d]>=0 && grid[i+dy[d]][j+dx[d]]=='1'){
                explore(grid,i+dy[d],j+dx[d]);
            }
        }
    }
}

以上代码中还可以利用一个trick，就是将explore函数的标记值”x“改为“0“，即将找到的小岛块先沉没下去，再找它周围的，继续沉。但是实际测试时发现没有提高多少效率，因为对于我们的查找来说，每次都是找”1“,所以”0“和”x“对于算法来说都是一样的。