题解 | #岛屿数量#

import java.util.*;

/**
 * NC109 岛屿数量
 * @author d3y1
 */
public class Solution {
    private boolean[][] isVisited;
    private int ROW;
    private int COL;
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};

    private int result = 0;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型二维数组
     * @return int整型
     */
    public int solve (char[][] grid) {
        return solution1(grid);
        // return solution2(grid);
    }

    /**
     * dfs
     * @param grid
     * @return
     */
    private int solution1(char[][] grid){
        ROW = grid.length;
        COL = grid[0].length;

        isVisited = new boolean[ROW][COL];

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                if(!isVisited[i][j]){
                    if(grid[i][j] == '1'){
                        dfs(grid, i, j);
                        result++;
                    }else{
                        isVisited[i][j] = true;
                    }
                }
            }
        }

        return result;
    }

    /**
     * dfs
     * @param grid
     * @param x
     * @param y
     */
    private void dfs(char[][] grid, int x, int y){
        if(!isVisited[x][y]){
            isVisited[x][y] = true;
            if(grid[x][y] == '1'){
                for(int i=0; i<4; i++){
                    if(isValid(x+dx[i], y+dy[i])){
                        dfs(grid, x+dx[i], y+dy[i]);
                    }
                }
            }
        }
    }

    /**
     * 是否合法(是否越界)
     * @param x
     * @param y
     * @return
     */
    private boolean isValid(int x, int y){
        if(x<0 || x>=ROW || y<0 || y>=COL){
            return false;
        }

        return true;
    }

    /**
     * bfs
     * @param grid
     * @return
     */
    private int solution2(char[][] grid){
        ROW = grid.length;
        COL = grid[0].length;

        isVisited = new boolean[ROW][COL];

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                if(!isVisited[i][j]){
                    if(grid[i][j] == '1'){
                        bfs(grid, i, j);
                        result++;
                    }else{
                        isVisited[i][j] = true;
                    }
                }
            }
        }

        return result;
    }

    /**
     * bfs
     * @param grid
     * @param x
     * @param y
     */
    private void bfs(char[][] grid, int x, int y){
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(x, y));
        Step step,next;
        while(!queue.isEmpty()){
            step = queue.poll();
            isVisited[step.x][step.y] = true;
            if(grid[step.x][step.y] == '1'){
                for(int i=0; i<4; i++){
                    next = new Step(step.x+dx[i], step.y+dy[i]);
                    if(isValid(next.x, next.y) && !isVisited[next.x][next.y]){
                        queue.offer(next);
                    }
                }
            }
        }
    }

    private class Step{
        int x;
        int y;

        public Step(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}