2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 社区与地区选拔赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：赫拉克利亚迷宫 (Лавиринтот во Хераклеја)

题目描述

在古城赫拉克利亚（Heraclea）的核心地带，考古学家发现了一个神秘的矩形迷宫蓝图。迷宫被表示为一个具有 $N$ 行和 $M$ 列的网格。网格中的每个单元格标记如下：

• . - 可通行的平地
• # - 墙壁

如果两个可通行的单元格具有公共边（上、下、左或右），则认为它们是连通的。一个或多个相互连通的可通行单元格构成一个房间（即连通分量）。

考古学家想要对迷宫进行一次“准重建”。为此，他们必须从网格中移除恰好一个完整行或一个完整列。移除后，该行或该列将完全消失，剩下的行或列会“合并”（空隙被关闭）。

显而易见，移除行或列会改变迷宫的外观，并且很可能改变房间的数量。

你有权选择移除哪一行或哪一列。你的目标是：通过选择移除某一行或某一列，使得迷宫中剩余的房间数量尽可能少。

题目并不要求输出具体移除哪一行或列，只需要输出移除后迷宫中房间数量的最小值。

输入格式

• 第一行包含两个整数 $N$ 和 $M$ ($2 \le N, M \le 2000$)。
• 接下来 $N$ 行，每行包含 $M$ 个字符（. 或 #），描述迷宫的初始布局。

评分说明：

• 24% 的测试点满足：$N = 2$。
• 另有 48% 的测试点满足：$N \le 200$。

输出格式

• 输出一个整数，代表删除一行或一列后，迷宫中可能剩下的最少房间数量。

限制条件

• 时间限制： 1 秒
• 内存限制： 64 MB

样例说明

样例 1： 输入：

3 3
###
###
...

输出：0

• 解释：如果移除第 3 行（全是平地的那行），剩下的两行全是墙壁，房间数为 0。

样例 2： 输入：

3 3
.#.
.#.
.#.

输出：1

• 解释：如果移除中间那一列（全是墙壁的那列），左右两列平地会合并在一起，形成 1 个大房间。

解题思路分析

这是一个关于图论连通性的问题，难点在于 $N, M$ 高达 2000，且内存限制较紧（64MB）。

1. 基本逻辑：移除第 $i$ 行后，原本在第 $i-1$ 行和第 $i+1$ 行的平地如果列坐标相同，则会直接接触并可能合并。
2. 复杂度挑战：
   • 暴力做法：尝试移除每一行/列，并对剩余图跑一次 BFS/DFS 或并查集。时间复杂度 $O((N+M) \cdot NM)$，即 $O(N^3)$，会严重超时。
   • 优化思路：利用并查集维护初始连通分量。当删除某一行 $i$ 时，计算第 $i-1$ 行与第 $i+1$ 行合并导致的连通分量变化。这通常涉及处理“由于中间层消失，原本不连通的两个分量现在连通了”的情况。
3. 内存建议：对于 2000x2000 的网格，使用 int 数组存储每个点的连通分量编号需占用 $2000 \times 2000 \times 4 \approx 16\text{MB}$。注意不要开启过多的辅助大数组以免超出 64MB。

版权信息

• 项目： Macedonian Programming Contests 2026
• 赛事： Community and Regional competition
• 版权方： Zidruženije na informatičari na Makedonija (ZIM / 北马其顿计算机科学家协会)