Java运用BFS（广度优先搜索）解决水塘问题（全英文）

Question

Overview: Your program will be given a "map" of wet and dry locations and you will determine how many
seperate puddles (contiguous wet areas) are depicted.
Details: The input will come from a le called input.txt which will be placed in the same directory as your
java le. The rst line of the le will have two integer values R and C which will be the number of rows and
columns in the map (simple rectangular region that can be represented by a 2-D array). Each of the next R
lines will consist of C zeroes or ones. A zero will indicate water and a one will indicate NOT water (grass?).
Two zeroes will be considered to be in the same puddle if they are either directly left/right of each other (ie
(i,j) and (i, j+1)) or directly above/below each other (ie (i,j) and (i+1, j)) or can be connected via repeated
applications of these rules.
Another (more technical) way to picture the situation is that you begin with a graph having R C vertices
each having label (i,j) where 0 i < R and 0 j < C and are divided into two sets ”Water" and “Not
Water". Vertex (i,j) shares an edge with the vertices above, below, left, and right, but not diagonal). In
other words, (i,j) is adjacent to vertices (i-1,j), (i,j-1), (i,j+1), and (i+1, j). You then remove all ”Not Water"
vertices and their incident edges.
Your program will output the number of puddles (or in the more technical description the number of com-
ponents in the graph).

Sample execution: If input.txt contains
5 10
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 1 1 1
1 1 1 0 0 0 0 1 1 1
then the output should be
1
If input.txt contains
10 15
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0 1 0 1
1 1 1 1 1 0 1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 0 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 0 1 0 1 0 1
the the output should be
12

Answer 1

class Solution {
    public static int numIsPools(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_ispools = 0;

        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == 0) {
                    ++num_ispools;
                    grid[r][c] = 1;
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == 0) {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = 1;
                        }
                        if (row + 1 < nr && grid[row+1][col] == 0) {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = 1;
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == 0) {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = 1;
                        }
                        if (col + 1 < nc && grid[row][col+1] == 0) {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = 1;
                        }
                    }
                }
            }
        }

        return num_ispools;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int col = scanner.nextInt();
        int line = scanner.nextInt();
        int[][] arr= new int[col][line];
        for(int i =0;i<col;i++){
            for (int j =0;j<line;++j){
                arr[i][j] = scanner.nextInt();
            }
        }
        System.out.println(numIsPools(arr));
    }
}

已自测，给个采纳吧