题解 | #岛屿数量#

package org.example.test;

import java.util.*;

public class BFSTest {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        int[][] test = {{1}};
        System.out.println(solve(test));
    }

    public static int solve(int[][] grid) {
        // write code here
        List<List<Boolean>> visited = new ArrayList<>();
        for (int[] ints : grid) {
            List<Boolean> tmp = new ArrayList<>();
            for (int j = 0; j < ints.length; j++) {
                tmp.add(false);
            }
            visited.add(tmp);
        }
        Queue<int[]> queue = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1 && !visited.get(i).get(j)) {
                    queue.offer(new int[]{i, j});
                    ans += BFS(grid, queue, visited);
                }
            }
        }
        return ans;
    }

    /**
     * 如果每次有遍历就说明当前是一个岛屿。
     * 使用队列保存未遍历的节点，节点表示为 int[x][y],
     * 使用visited数组保存遍历过的节点，
     * 当遇到节点为1的时候，如果没有遍历则为一个岛屿，
     * 采用BFS广度有限遍历方式，会把周围为1的节点遍历完，
     * 所有节点遍历完，岛屿就统计出来。
     *
     * @param grid
     * @param queue
     * @param visited
     * @return
     */
    private static int BFS(int[][] grid, Queue<int[]> queue, List<List<Boolean>> visited) {
        int ans = 0;
        while (!queue.isEmpty()) {
            ans++;
            int[] xy = queue.poll();
            visited.get(xy[0]).set(xy[1], true);
            for (int i = 0; i < 4; i++) {
                int x = xy[0] + dx[i];
                int y = xy[1] + dy[i];
                if (!(x >= 0 && y >= 0 && x < grid.length && y < grid[x].length)) {
                    continue;
                }
                if (!visited.get(x).get(y)) {
                    if (grid[x][y] == 1) {
                        int[] tmp = new int[2];
                        tmp[0] = x;
                        tmp[1] = y;
                        queue.offer(tmp);
                    }
                }
            }
        }
        return ans > 0 ? 1 : 0;
    }
}