package leecode;

/**
 * 岛屿数量
 *
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *
 * 此外，你可以假设该网格的四条边均被水包围。
 *
 * 2021/5/19
 * @author tang
 */
public class NumIslands {

    /**
     * 思路：
     * 遍历二维数组 每个1(陆地) 如果统计过了 就改为x,并将递归的将周围的1改为x
     * 判断每个元素如果是0(水) 就忽略
     * 如果是1(陆地) 判断其上下左右是否有-1,如果有说明和之前的陆地连着了
     * 如果没有 说明是新陆地 统计岛屿数+1
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int countLand = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                //元素是陆地的情况
                if(grid[i][j] == '1'){
                    //孤独的一块陆地
                    if(isAlonePlace(grid, i, j)){
                        countLand++;
                    }
                    changeToX(grid, i, j);

                }
            }

        }
        return countLand;
    }

    /**
     * 这块地前后左右是不是没有x(和已经统计过的连着呢)
     * @return
     */
    private boolean isAlonePlace(char[][] grid, int x, int y){
        //上
        if(x-1 >= 0 && grid[x-1][y] == 'x'){
            return false;
        }
        //下
        if(x+1 < grid.length && grid[x+1][y] == 'x'){
            return false;
        }
        //左
        if(y-1 >= 0 && grid[x][y-1] == 'x'){
            return false;
        }
        //右
        if(y+1 < grid[x].length && grid[x][y+1] == 'x'){
            return false;
        }
        return true;
    }

    /**
     * 递归的将该坐标从1改成x
     */
    private void changeToX(char[][] grid, int i, int j){
        //越界情况
        if(i < 0 || i > grid.length-1 || j < 0 || j > grid[i].length-1){
            return;
        }
        if(grid[i][j] == '0' || grid[i][j] == 'x'){
            return;
        }
        //合法情况下 将当前该点设置为x
        grid[i][j] = 'x';

        //继续向下递归他的上下左右
        changeToX(grid,i-1, j);
        changeToX(grid,i+1, j);
        changeToX(grid, i, j-1);
        changeToX(grid, i, j+1);
    }

    public static void main(String[] args) {
        char[][] grid = {
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
//                {'1','1','1'},
//                {'0','1','0'},
//                {'1','1','1'}

        };
        System.out.println(new NumIslands().numIslands(grid));
    }

}