2018秋-阿里巴巴-编程题2

2017年5月18日，国土资源部中国地质调查局昨日在南海宣布,我国正在南海北部神狐海域进行的可燃冰试采获得成功。准备用一个NN的地图来标记这些可燃冰的位置，图中用标示了可燃冰的存在，冰田有大有小，地图上两个点之间可以直接连成直线的认为是同一块冰田，但不能通过其它非冰田的区域。例如：

上图中有一块冰田

上图中有两块冰田，左上角为第一块，右下角3个*由于每两点之间可以通过直线连通，算作一块冰田，为第二块。

当输入一个二维数组（里面包含了和0）地图的时候，可以输出冰田的数量。输入第一行为二维数组的大小，例如4，表示44的地图。后面每一行为二维数组的实际内容。

/*解题思路：递归
首先从第一行第一列开始遍历，找到第一个等于1的元素grid[i,j]，将其定义为一个岛，那这个冰田能不能向外扩展呢，就要看包围grid[i,j]的八个元素是不是也等于1，
如果右面的元素grid[i,j+1]也等于1说明岛可以像右扩展，同理判断其余八个元素，八个元素每个又都存在各自的四邻，当所有向外扩展的点都不能继续扩展的时候就找到了一个冰田，
所以这是一个递归的过程，在递归的同时我们需要有一个标识来标记这个元素是否被访问过，否则的话递归就没有出口了，为了节省存储空间可以改变访问过的元素的值来表示该元素是否被访问，
而改变的值我们也可以定义成当前已经找出来的冰田的个数。*/
public class Solution {  
    public int numIslands(char[][] grid) {  
        int num = 0;  
        for(int i = 0; i < grid.length; i++) {  
            for(int j = 0; j < grid[0].length; j++) {  
                if(grid[i][j] != '1') continue;  
                dfs(grid, i, j);  //dfs 和 bfs 结合，将 (i,j)及附近能联通的所有值为1的点值置为1  
                num++;  
            }  
        }  
        return num;  
    }  
    private void dfs(char[][] grid, int i, int j) {  //dfs深度遍历  
        if(i >= grid.length || i < 0 || j < 0 ||  
            j >= grid[0].length || grid[i][j] != '1') return;  
        grid[i][j] = '2';  
        dfs(grid, i+1, j);  //右 dfs 整体看来是 bfs  
        dfs(grid, i, j+1);  //下
        dfs(grid, i-1, j);  //左
        dfs(grid, i, j-1);  //上
        dfs(grid, i-1, j-1);
        dfs(grid, i-1, j+1);
        dfs(grid, i+1, j-1);
        dfs(grid, i+1, j+1);
    }  
}