200. 岛屿数量

思路

这里棕色代表陆地，蓝色代表海洋

从数组中第一个元素找起，此时其数值为1，所以找到了一个陆地，关键是将关联的陆地进行标记，这样在找下一个岛屿的过程中才不会重复
这个过程就是floodfill的过程
其实就是从初始点开始进行一次深度优先遍历
一旦找到相邻的而且是陆地并且没有标记过，则进行标记

依次可得



对于此此时第5个点都考虑过了，此时进行回退，一直到第一行第2个点，此时向下标记




此时标记完成，逐步退回到第一个点
对于多个岛屿

先标记上第一个岛屿，然后找到第一个没被标记的陆地，继续标记

这里的很多技术与上一节的很多方法都是一样的

code

class Solution {
    private int[][] d = {{0,1},{1,0},{0,-1},{-1,0}};
    private int m,n;
    private boolean[][] visited;
    boolean inArea(int x,int y){
        return x>=0&&x<m&&y>=0&&y<n;
    }
    //从grid[x][y]的位置开始，进行floodfill 将相连的土地进行标记
    private void dfs(char[][] grid,int x,int y){
        //设为已经访问过
        visited[x][y]=true;
        //四个方向进行标记
        for(int i=0;i<4;i++){
            int newx = x + d[i][0];
            int newy = y + d[i][1];
            //如果新的土地位置合法并且没有被访问过 则对新的位置进行dfs
            if(inArea(newx,newy)&&!visited[newx][newy]&&grid[newx][newy]=='1')
                dfs(grid,newx,newy);
        }   
        //如果都没有找到 则返回
        return;
    }
    public int numIslands(char[][] grid) {
        m = grid.length;
        //特殊条件判断
        if(m==0)
            return 0;
        n = grid[0].length;
        visited =  new boolean[m][n];
        int res = 0;
        //遍历第一个没访问过的陆地
        for(int i=0;i<m;i++){
            for(int j=0;j<grid[i].length;j++){
                //找到一个新的岛屿
                if(grid[i][j]=='1'&&!visited[i][j]){
                    res++;    
                    dfs(grid,i,j);   //进行floodfill标记 将同属于同一块岛屿的陆地设为已经访问过
                }
            }
        }
        return res;
    }
}