洪水淹没算法

695. 岛屿的最大面积

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res =0;
        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    res=Math.max(res,FloodFill(grid,i,j));
                }
            }
        }
        return res;
    }
    //淹没与i,j相邻的陆地并记录下面积
    int FloodFill(int[][] grid,int i, int j){
        if(!isValid(i,j,grid)) return 0;
        if(grid[i][j]==0) return 0;
        grid[i][j]=0;
        return FloodFill(grid,i+1,j)
        +FloodFill(grid,i,j+1)
        +FloodFill(grid,i-1,j)
        +FloodFill(grid,i,j-1) +1;

    }
    boolean isValid(int i,int j,int[][] grid){
        if(i>=0 && j>=0 && i<grid.length && j<grid[0].length){
            return true;
        }
        return false;
    }
}

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

class Solution {
    //二维数组的递归遍历和floodfill算法
    public int numIslands(char[][] grid) {
        int res =0;
        int m = grid.length;
        int n = grid[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == '1'){
                    res++;
                    FloodFill(grid,i,j);
                }
            }
        }
        return res;
    }
    //洪水填充算法，将1周围的所有1都改变为0，最终使得图中的1的数目便是岛屿的数目
    void FloodFill(char[][] grid, int i, int j){
        if(!isValid(i,j,grid)) return;
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        FloodFill(grid,i+1,j);
        FloodFill(grid,i,j+1);
        FloodFill(grid,i-1,j);
        FloodFill(grid,i,j-1);
    }
    boolean isValid(int i,int j,char[][] grid){
        if(i>=0 && j>=0 && i<grid.length && j<grid[0].length){
            return true;
        }
        return false;
    }
}