题解 | 剪纸游戏

import java.io.*;
import java.util.*;

public class Main {
    /**
     * 主方法，用于读取输入数据并处理网格问题
     *
     * @param args 命令行参数
     * @throws IOException 可能抛出的IO异常
     */
    public static void main(String[] args) throws IOException {

        // 使用BufferedReader读取输入流
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 使用PrintWriter输出结果
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取第一行输入并分割成字符串数组
        String[] str = br.readLine().trim().split("\\s+");
        // 解析网格的行数n
        int n = Integer.parseInt(str[0]);
        // 解析网格的列数m
        int m = Integer.parseInt(str[1]);

        // 创建n行m列的字符网格
        char[][] grid = new char[n][m];

        // 逐行读取网格数据
        for (int i = 0; i < n; i++) {
            // 将每行字符串转换为字符数组存入网格
            grid[i] = br.readLine().toCharArray();
        }

        // 创建n行m列的访问标记数组，初始值都为false
        boolean[][] visit = new boolean[n][m];
        // 初始化答案计数器
        int ans = 0;

        // 遍历网格的每个单元格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果当前单元格是'.'且未被访问过
                if (grid[i][j] == '.' && !visit[i][j]) {
                    // 使用BFS方法处理，如果返回true则增加答案计数
                    if (bfs(grid, n, m, i, j, visit)) {
                        ans++;
                    }

                }
            }
        }
        // 输出最终结果
        out.println(ans);
        // 刷新输出流
        out.flush();
        // 关闭输出流
        out.close();
        // 关闭输入流
        br.close();

    }


    /**
     * 使用广度优先搜索(BFS)算法遍历连通区域，并判断该连通区域是否为矩形
     *
     * @param grid  二维字符网格，其中'.'表示可走区域
     * @param n     网格的行数
     * @param m     网格的列数
     * @param i     起始点的行坐标
     * @param j     起始点的列坐标
     * @param visit 记录访问状态的二维数组
     * @return 如果连通区域是完整的矩形则返回true，否则返回false
     */
    private static boolean bfs(char[][] grid, int n, int m, int i, int j, boolean[][] visit) {
        // 使用队列进行BFS遍历
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visit[i][j] = true;  // 标记起始点为已访问

        // 记录连通区域的最小和最大x、y坐标
        int minX = i, maxX = i;
        int minY = j, maxY = j;

        // 记录连通区域中点的数量
        int count = 0;

        // 定义四个方向的偏移量：上、下、左、右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // BFS遍历连通区域
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();  // 取出队列中的当前点
            int x = cur[0];
            int y = cur[1];

            count++;  // 增加连通区域点计数

            // 更新连通区域的边界
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);

            // 遍历四个方向
            for (int k = 0; k < 4; k++) {
                int nextX = x + dx[k];
                int nextY = y + dy[k];

                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && grid[nextX][nextY] == '.' && !visit[nextX][nextY]) {
                    visit[nextX][nextY] = true;
                    queue.add(new int[]{nextX, nextY});
                }
            }

        }

        // 判断是否填满整个区域
        // 当count等于整个区域的格子数量时，返回true，表示已填满
        // 整个区域的格子数量计算公式为：(maxX-minX+1) * (maxY-minY+1)
        return count == (maxX - minX + 1) * (maxY - minY + 1);
    }
}