把格子看成顶点、公共边无墙处连边，一次洪水填充求出房间数、最大房间和各房间编号；再扫每个右邻/下邻房间号不同的位置枚举所有可拆墙，用元组（合并大小, -2x, 2y）一次比较就把最大值与「先西后南」的平局规则一起解决，O(MN)。
OJ: roj
题目 ID: 2021
难度:普及+/提高-
标签:图论连通块洪水填充网格python
创建: 2026-10-01 03:20
更新: 2026-10-07 13:50
形式化题目
给定
两个共享一条边、且公共边上没有墙的格子视为连通，该连通关系把网格划分成若干房间。要求输出：
- 房间的个数；
- 最大房间包含的格子数；
- 拆掉一面内部墙之后能得到的最大房间格子数；
- 这面墙的位置：由与它相邻的、靠西的格子命名（竖墙，记
E）或靠南的格子命名（横墙，记N），行列号从开始。
如果有多面墙并列最优，先取中点最靠西的那面，若仍并列则取中点最靠南的那面。
下面对样例第 1 组（
列: 1 2 3 4 5 6 7
行 1: 1 1 2 2 3 3 3
行 2: 1 1 1 2 3 4 3
行 3: 1 1 1 5 3 5 3
行 4: 1 5 5 5 5 5 3一共 5 间房，大小分别是
正解
思路
第一步是看图。 把每个小正方形当成一个顶点，两个相邻格子之间没有墙就连一条边。
"没有墙"是互反的——
- 第 1 问 = 连通分量个数；
- 第 2 问 = 最大连通分量的大小（顶点数）。
连通分量用一次洪水填充就能全部求出。按行优先顺序扫描，遇到还没编号的格子就开一个新的房间号 rid，
用栈把从它出发、只走无墙边能到达的格子全部标上同一个 rid。
最坏情况下（例如大房间连成蛇形）递归深度会达到
第二个观察才是本题真正的技巧。 第 3、4 问要枚举所有可拆的墙，直觉上需要遍历每面墙、
去两侧格子各自的编码里查这一位是不是
若两个相邻格子的房间号不同，则它们之间的公共边上一定有墙。
证明很直接：洪水填充是顺着每一条无墙的边扩散的，所以填充结束时，任何一条无墙边的两侧格子 必然拿到同一个房间号；反过来，房间号不同就说明这条边上有墙。这个方向是充分的， 而下面的枚举只用到这个方向。
注意反方向并不成立：同一个房间内部完全可以还立着多余的墙。样例第 1 组就有 3 处这样的地方——
例如
这种多余的墙拆掉之后两格本来就已连通，房间不会变大，得到的房间大小仍是
所以只要逐格检查右邻和下邻的房间号是否不同：不同就说明中间必定隔着一面墙， 而所有能让房间变大的墙都会在这里被枚举到。这省掉了对每面墙做两次编码校验。
接下来是"拆一面墙有多大收益"。设这面墙两侧的房间是
因为拆墙只可能把
最后是平局规则。 题面要求先比"最靠西"，再比"最靠南"，并在编者注里明确：墙的位置由它的中点定义。
用 0 起始的行列号
- 竖墙：
，题面命名为" 的西墙"，符号 E； - 横墙：
，题面命名为" 的北墙"，符号 N。
注意两者的命名格子不同：竖墙用靠西的格子（列号
"最靠西"是中点横坐标最小，"然后最靠南"是中点纵坐标最大。为避免浮点运算，把所有中点坐标乘 2， 把每个候选墙压成一个元组：
其中 max 同时回答第 3、4 两问，不必先收集再排序。
样例中合并值最大的墙有 4 面（都是
| 墙（中点） | 合并后大小 | 输出形态 | ||
|---|---|---|---|---|
| 16 | 6 | 4 3 N |
||
| 16 | 6 | 4 2 N |
||
| 16 | 5 | 3 3 E |
||
| 16 | 7 | 4 1 E ← 选中 |
四者的第一项都是
代码
Python 版：
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:20
# update_at: 2026-10-01 03:26
import sys
from collections.abc import Iterator
WEST, NORTH, EAST, SOUTH = 1, 2, 4, 8 # 题面的墙编码：1 西 2 北 4 东 8 南
AROUND = ((-1, 0, NORTH), (1, 0, SOUTH), (0, -1, WEST), (0, 1, EAST)) # (dy, dx, 该边有墙时的编码)
def label_rooms(grid: list[list[int]], n: int, m: int) -> tuple[list[int], list[int]]:
"""洪水填充：返回 (每个格子的房间号, 每个房间的格子数)。"""
room, sizes = [-1] * (n * m), []
for start in range(n * m):
if room[start] >= 0:
continue
rid = len(sizes) # 房间号就是它被发现的顺序，同时也能当 sizes 的下标
room[start], stack, size = rid, [start], 0
while stack: # 显式栈，避免格子连成蛇形时递归过深
y, x = divmod(stack.pop(), m)
size += 1
v = grid[y][x]
for dy, dx, wall in AROUND:
ny, nx = y + dy, x + dx
if not (0 <= ny < n and 0 <= nx < m):
continue # 邻居在城堡外
if v & wall or room[ny * m + nx] >= 0:
continue # 这条边有墙，或邻居已经归属某个房间
room[ny * m + nx] = rid
stack.append(ny * m + nx)
sizes.append(size)
return room, sizes
def removable_walls(room: list[int], sizes: list[int], n: int, m: int) -> Iterator[tuple[int, int, int, str]]:
"""产出每一面可拆的墙：(合并后的房间大小, -2x, 2y, 墙名)，其中 (x, y) 是墙的中点。
洪水填充顺着无墙边扩散，所以相邻两格房间号不同就说明中间隔着墙（反之不成立：
房间内部可能还立着多余的墙，拆它不会让房间变大，跳过即可）。
竖墙（E）用西侧格子命名，横墙（N）用南侧格子命名；中点坐标都乘 2 是为了把半整数变成整数。
"""
for y in range(n):
for x in range(m):
here = room[y * m + x]
if x + 1 < m and room[y * m + x + 1] != here: # 拆竖墙：东西两间房合并
merged = sizes[here] + sizes[room[y * m + x + 1]]
yield merged, -(2 * x + 2), 2 * y + 1, f"{y + 1} {x + 1} E"
if y + 1 < n and room[(y + 1) * m + x] != here: # 拆横墙：南北两间房合并
merged = sizes[here] + sizes[room[(y + 1) * m + x]]
yield merged, -(2 * x + 1), 2 * y + 2, f"{y + 2} {x + 1} N"
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
m, n = next(data), next(data) # 先给列数 M，再给行数 N
grid = [[next(data) for _ in range(m)] for _ in range(n)]
room, sizes = label_rooms(grid, n, m)
# 元组的字典序比较天然实现了题面的三级规则：合并大小 → 中点越靠西 → 中点越靠南
merged, _neg2x, _y2, name = max(removable_walls(room, sizes, n, m))
print(len(sizes))
print(max(sizes))
print(merged)
print(name)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 09:17
* update_at: 2026-10-06 09:17
*/
#include <cstdio>
#include <string>
using namespace std;
const int MAXN = 55; // 网格最大 50 x 50，留一点余量
const int MAXROOM = 2600; // 最多 50*50 个房间，每个格子独立成一间
const int WEST = 1; // 题面的墙编码：1 西 2 北 4 东 8 南
const int NORTH = 2;
const int EAST = 4;
const int SOUTH = 8;
int m, n; // m 为列数 M，n 为行数 N
int grid[MAXN][MAXN]; // grid[r][c] 是格子 (r,c) 的墙编码，行列均从 0 开始
int room[MAXN][MAXN]; // room[r][c] 是格子 (r,c) 所属的房间号，-1 表示未访问
int sizes[MAXROOM]; // sizes[i] 是第 i 间房的格子数，下标即房间号
int stack_y[MAXN * MAXN]; // 洪水填充的显式栈，避免蛇形大房间递归过深
int stack_x[MAXN * MAXN];
int room_cnt; // 房间总数
// 四个方向：偏移量与"这条边有墙"时对应的墙编码。
int dir_y[4] = {-1, 1, 0, 0};
int dir_x[4] = {0, 0, -1, 1};
int dir_wall[4] = {NORTH, SOUTH, WEST, EAST};
// 洪水填充：把整个网格划分成房间，同时统计每间房的格子数。
void label_rooms() {
room_cnt = 0;
for (int start = 0; start < n * m; start++) {
int sr = start / m;
int sc = start % m;
if (room[sr][sc] >= 0) {
continue;
}
int rid = room_cnt;
room_cnt++;
int top = 0;
stack_y[top] = sr;
stack_x[top] = sc;
top++;
room[sr][sc] = rid;
int size = 0;
while (top > 0) {
top--;
int y = stack_y[top];
int x = stack_x[top];
size++;
int v = grid[y][x];
// 顺着四条无墙的边扩散
for (int d = 0; d < 4; d++) {
if ((v & dir_wall[d]) != 0) {
continue; // 这条边有墙，走不过去
}
int ny = y + dir_y[d];
int nx = x + dir_x[d];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
continue; // 邻居在城堡外
}
if (room[ny][nx] >= 0) {
continue; // 邻居已归属某间房
}
room[ny][nx] = rid;
stack_y[top] = ny;
stack_x[top] = nx;
top++;
}
}
sizes[rid] = size;
}
}
int main() {
scanf("%d%d", &m, &n);
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
scanf("%d", &grid[r][c]);
room[r][c] = -1;
}
}
label_rooms();
// 洪水填充顺着无墙边扩散，所以相邻两格房间号不同就说明中间隔着墙。
// 只需比较房间号，不必再查墙的编码。
int best_merged = -1;
int best_neg2x = 0; // -2x 越大，墙的中点越靠西
int best_y2 = -1; // 2y 越大，墙的中点越靠南
int best_r = 0; // 输出用的行列号，从 1 开始
int best_c = 0;
char best_wall = 'E';
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
int here = room[r][c];
// 拆竖墙：格 (r,c) 与 (r,c+1) 合并，题面用西侧格子命名，记 E
if (c + 1 < m && room[r][c + 1] != here) {
int other = room[r][c + 1];
int merged = sizes[here] + sizes[other];
int neg2x = -(2 * c + 2); // 中点横坐标 x = c+1
int y2 = 2 * r + 1; // 中点纵坐标 y = r+0.5
if (merged > best_merged ||
(merged == best_merged && neg2x > best_neg2x) ||
(merged == best_merged && neg2x == best_neg2x && y2 > best_y2)) {
best_merged = merged;
best_neg2x = neg2x;
best_y2 = y2;
best_r = r + 1;
best_c = c + 1;
best_wall = 'E';
}
}
// 拆横墙：格 (r,c) 与 (r+1,c) 合并，题面用南侧格子命名，记 N
if (r + 1 < n && room[r + 1][c] != here) {
int other = room[r + 1][c];
int merged = sizes[here] + sizes[other];
int neg2x = -(2 * c + 1); // 中点横坐标 x = c+0.5
int y2 = 2 * r + 2; // 中点纵坐标 y = r+1
if (merged > best_merged ||
(merged == best_merged && neg2x > best_neg2x) ||
(merged == best_merged && neg2x == best_neg2x && y2 > best_y2)) {
best_merged = merged;
best_neg2x = neg2x;
best_y2 = y2;
best_r = r + 2;
best_c = c + 1;
best_wall = 'N';
}
}
}
}
int max_size = 0;
for (int i = 0; i < room_cnt; i++) {
if (sizes[i] > max_size) {
max_size = sizes[i];
}
}
printf("%d\n", room_cnt);
printf("%d\n", max_size);
printf("%d\n", best_merged);
printf("%d %d %c\n", best_r, best_c, best_wall);
return 0;
}复杂度
- 时间复杂度：洪水填充每个格子入栈一次、每格查 4 个方向，
； 枚举候选墙扫每个格子的右邻与下邻， ； max再线性扫一遍，仍是。总计 。 - 空间复杂度：
room一维数组、显式栈与sizes各，总计 。
总结
- 建模：格子是顶点，"公共边无墙"是边，房间就是无向图的连通分量；前两问是分量计数与最大分量大小。
- 关键观察：两个相邻格子的房间号不同
它们之间隔着一面墙。有了它，枚举可拆墙时完全不必读墙的编码， 只需比较房间号。（反向不成立：房间内部可以有多余的墙，拆它收益为 0，跳过即可。） - 收益公式：拆一面墙的收益恰为两侧房间大小之和，所以第 3 问退化成一次线性取最大。
- 平局规则：按题面的编辑注，比较的是墙的中点，且方向是"先西后南"。
把中点半坐标乘 2 后压进元组
(合并大小, -2x, 2y)，Python 的元组比较就把三级规则一次做完。 - 命名易错点：竖墙
E用靠西格子的列号（），横墙 N用靠南格子的行号（），两者不对称。