The Castle题解：Flood Fill、位掩码与拆墙优先级全解析

最近集中刷《信息学奥赛一本通》的搜索专题，做到 1250 The Castle 这题时，我忍不住给这题盖了个“狠”字。第一眼看上去就是个标准 Flood Fill 连通块计数题，把房间数和最大房间求出来就算完，结果第三问在输出拆墙方案时，优先级这个细节硬是让我改了三次才过。如果你也是刷一本通卡在这题，大概率不是不会搜索，而是被“最西、最南、优先方向”这种排列组合式的输出规则折磨过。

这题适合两类人看：一类是刚开始学 DFS/BFS 连通块，想找模板题练手的；另一类是已经会 Flood Fill，但第三问老是在边界条件或输出顺序上踩坑的。我会把题目怎么读、墙的状态怎么拆、Flood Fill 怎么写、第三问的优先级怎么理解全部拆开讲，顺便附上我调试时踩过的几个坑。保证你读完能一次 AC，不用再体验那种“样例过了却 WA 到怀疑人生”的感觉。

1. 题目到底在说什么：读懂 The Castle

1.1 题面与输入输出格式

这道题本质上给你一张“城堡平面图”，城堡被划分成 (m \times n) 个大小相等的方格模块，每个模块周围可能有墙，也可能没有墙。墙的存在与否不是直接告诉你哪个方向有墙，而是用一个整数表示，这个整数的二进制位上藏着四面墙的信息。

题目给定一个用数字矩阵描述的城堡：

4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13

第一行两个数分别是城堡的行数 (m) 和列数 (n)，后面跟着 (m) 行，每行 (n) 个整数。每个整数代表对应方格四周墙的分布情况。

输出要求分成四行：

1. 城堡有多少个房间；
2. 最大房间的面积（也就是最多包含多少个方格）；
3. 拆除一面墙之后，能得到的最大的房间面积；
4. 拆除哪一面墙可以得到这个最大面积，格式为“行号 列号 方向”，方向用N表示北墙，E表示东墙。

上面样例对应的正确输出是：

5 9 16 4 1 E

也就是说，这个城堡有 5 个房间，最大房间面积是 9，拆一面墙后最多能合并出 16 个格子的房间，这个最优拆墙点是第 4 行第 1 列，拆掉它的东墙。

1.2 为什么说它是“狠题”

如果只做前两问，这题就是一个很朴素的连通块统计。但从第三问开始，题目就开始“作妖”了。

第三问的难点不在于找“哪面墙拆了合并面积最大”，而在于当出现多个墙拆掉后面积都一样大时，要按照一个很具体的规则挑一个：

• 第一步，优先选择最靠西的墙，也就是列号最小的那个；
• 第二步，如果列号一样，选择最靠南的墙，也就是行号最大的那个；
• 第三步，如果还是分不出胜负，选择北墙N，而不是东墙E。

这个优先级里最容易被忽略的是“先列后行”。按理说地图遍历我们习惯从左上角开始按行扫，但这题偏偏要先保证列号最小，再保证行号最大。如果你傻乎乎地从第 1 行往第 m 行扫，再把行最大的覆盖上去，结果很容易错；如果你用“最后更新的答案覆盖前面的答案”这种方式，扫描顺序一旦反了，正确方案就会被错误方案顶掉。

我自己第一次做的时候就是按常规思路从左上往右下遍历，只在面积更大的时候更新答案，结果输出来的拆墙点和标准答案不一样。后来老老实实按“列从小到大、行从大到小、同格先检查北墙再检查东墙”的顺序枚举，一遍就过了。

2. 核心原理：为什么墙要用 1、2、4、8 编码

2.1 一个整数怎么表示四面墙

题目里每个格子给的数字不是一个单纯的“墙的数量”，而是一个位掩码（bitmask）。约定是这样的：

如果一个格子的数字是 11，那么它的二进制是1011，也就是：

• 最低位是 1，代表西墙存在；
• 第二位是 1，代表北墙存在；
• 第三位是 0，代表东墙不存在；
• 最高位是 1，代表南墙存在。

所以数字 11 表示这个格子“西、北、南”三面有墙，只有东面开口。

为什么要用 1、2、4、8 而不是 1、2、3、4？因为它们分别是 2 的 0、1、2、3 次幂，正好对应二进制不同的位。这样任意几面墙的组合，都可以用一个唯一的整数表示。比如“西墙和北墙都有”就是 (1 + 2 = 3)，二进制0011；“四墙都有”就是 (1 + 2 + 4 + 8 = 15)，二进制1111；“四面全空”就是 0。

这种编码方式在算法题里非常常见，叫做状态压缩。The Castle 只是用它表示墙，后面你会遇到更多用它表示开关状态、背包状态、迷宫状态的题目。所以这题虽然是个搜索题，顺带把位运算复习一下也很值。

2.2 判断有没有墙，要用位运算

有了位掩码，判断一个格子某个方向有没有墙，最简单的方法是做“按位与”：

bool hasWest = (x & 1) != 0; bool hasNorth = (x & 2) != 0; bool hasEast = (x & 4) != 0; bool hasSouth = (x & 8) != 0;

如果你要用这个格子能不能往某个方向走，就判断对应方向是不是 0。例如从当前格子往北走，条件是“北墙不存在”，也就是(x & 2) == 0。

这里有一个初学者特别容易犯的错：直接用取模或者判断数字等于某个值。比如看到 3 就以为只有“西、北墙”，但 3 也可能是别的组合，直接用==判断非常容易漏情况，正确姿势永远是位与。每次看到这种题目，我习惯先把位运算函数写好，减少后面写搜索时出错的概率。

2.3 方向数组配合位运算

搜索的时候要遍历四个方向，我会把方向数组和墙位一一对应：

// 方向: 0-西, 1-北, 2-东, 3-南 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int wallBit[4] = {1, 2, 4, 8};

这样在 BFS/DFS 时，想从当前格子走某个方向，直接检查(grid[x][y] & wallBit[i]) == 0就知道能不能走。这个对应关系一定要和方向数组对齐，一旦写乱，后面调试白天都找不出问题。

3. 房间数与最大房间：Flood Fill 实现

3.1 搜索思路

房间就是由“无墙通道”连成的连通块。我们把整个城堡看成一个 (m \times n) 的图，每个格子是一个节点，两个格子之间如果没有墙，就有一条边。

要统计房间数和最大房间面积，标准的做法是 Flood Fill，也就是从一个未访问的格子出发，顺着能走的格子一路标记，走完一个连通块就相当于找到一间房。整个过程可以用 DFS 也可以 BFS：

1. 初始化房间编号roomId = 0，面积数组area。
2. 从左上角开始遍历所有格子。
3. 如果当前格子没访问过，就从这个格子开始 DFS/BFS，把能连通的格子全部标记成同一个房间编号，同时记录这块连通块里有多少个格子。
4. 每结束一次搜索，房间数roomId加一，当前连通块大小存入area[roomId]。
5. 最后房间数就是连通块个数，最大面积就是area数组里的最大值。

这里我额外建议把每个格子属于哪个房间也存下来，用一个二维数组belong[x][y]记录。前两问确实只需要面积，但第三问要判断两面墙是不是属于两个房间，有belong数组会方便很多。

3.2 参考代码：前两问用 DFS 染色

因为《信息学奥赛一本通》的读者基本都是 C++ 选手，我直接给 C++ 实现。先看前两问的核心部分：

#include <bits/stdc++.h> using namespace std; int m, n; int castle[55][55]; int belong[55][55]; int area[2510]; int roomCnt = 0; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int wallBit[4] = {1, 2, 4, 8}; void dfs(int x, int y, int id) { belong[x][y] = id; area[id]++; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (belong[nx][ny] != 0) continue; if (castle[x][y] & wallBit[k]) continue; // 当前格子的该方向有墙 dfs(nx, ny, id); } } int main() { cin >> m >> n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> castle[i][j]; } } int maxArea = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (belong[i][j] == 0) { roomCnt++; area[roomCnt] = 0; dfs(i, j, roomCnt); maxArea = max(maxArea, area[roomCnt]); } } } cout << roomCnt << "\n"; cout << maxArea << "\n"; return 0; }

这段代码里最关键的判断是这一行：

if (castle[x][y] & wallBit[k]) continue;

它检查的是当前格子朝k方向有没有墙。如果有墙，就不能往那边走；如果没有墙，且目标格子没访问过，就继续 DFS。

3.3 为什么递归 DFS 在这题没问题

有人可能会问，DFS 递归深度会不会爆栈？这题的 (m, n) 上限一般都在 50 左右，最多 2500 个格子，递归深度最大就是 2500。C++ 默认栈空间是够用的，所以放心用递归。

不过我在写的时候还是推荐一个习惯：如果题目给的规模更大，比如 (m, n) 到了 1000，就不要用递归 DFS，改用 BFS 队列或者显式栈。Flood Fill 本质上不挑写法，DFS、BFS、并查集都能做。你要是只会 BFS，也完全没问题。核心是保证每个格子只进队/入栈一次，复杂度是 (O(mn))，最多也就 2500 个格子，怎么折腾都行。

另外，注意belong数组我从 1 开始编号房间，0 表示未访问。这样写有个好处，后面第三问判断两个格子是不是同一个房间，直接比较belong[x][y]是否相等就行，非常干净。

4. 第三问：拆哪面墙？优先级才是狠点

4.1 找候选墙的基本方法

前两问已经把每个格子所属的房间号记录下来了。第三问要拆一面墙，让两个房间合并成一个大房间。

我们不需要真的去模拟“拆墙”再重新 Flood Fill。因为拆墙的本质就是让两个原本不同的连通块合并，合并后的面积就是两个房间面积之和。所以只要枚举相邻两个不同房间之间的墙，计算area[a] + area[b]，取最大值即可。

具体枚举方式有两种：

1. 枚举所有格子，对每个格子检查东墙和北墙；
2. 枚举所有格子，检查四个方向，但注意每个墙会被重复统计，需要用belong不同来避免重复更新。

我推荐第一种，因为题目最终只需要输出N或E，检查北墙和东墙就能覆盖所有水平墙和垂直墙。你可能会想，那南墙和西墙怎么办？其实一面墙是两个格子共有的。比如第 2 行第 3 格子的南墙，就是第 3 行第 3 格子的北墙，所以在枚举时检查“上面格子的北墙”就会覆盖到它；同样，某个格子的西墙，就是左边格子的东墙。只检查北墙和东墙，所有墙恰好被覆盖一次，不会漏，也不会重复。

枚举时要注意一个前提：两个格子必须属于不同的房间。如果属于同一个房间，它们中间的那面“墙”其实不存在，或者拆了也没意义，因为本来就在同一个连通块里。

4.2 优先级到底怎么理解

这是全题最阴间的部分。当拆不同墙得到的最大面积相同时，题目要求输出：

• 最靠西：列号最小；
• 如果列号相同：最靠南：行号最大；
• 如果还相同：优先输出北墙N，而不是东墙E。

要让代码天然满足这个顺序，最稳的枚举循环是：

for (int j = 0; j < n; j++) { // 先枚举列，保证列号小的先被考虑 for (int i = m - 1; i >= 0; i--) { // 在同一列中，从下往上枚举，保证行号大的先被考虑 // 先检查 N 墙，再检查 E 墙 } }

也就是先列后行，列从小到大；行从大到小。这样第一个遇到的“最大合并面积”的候选墙，就是题目要求的最优解。然后在更新答案时，只在当前面积严格大于已有最优面积时才更新，不取大于等于，这样前面的优先级就不会被后面的平局结果覆盖。

这里容易搞混的点是：很多人习惯了双层循环for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ... } }，也就是先遍历行再遍历列。这样虽然能保证行号小的先出现，但“最靠西”要求的是列号最小，当两个候选墙行不同但列相同时，按行优先的扫描可能先处理了上面的格子，又因为题目还要行号最大，所以必须在最后用>=或者改遍历顺序。改遍历顺序是最不容易出错的。

我自己调试的时候就是在这个地方卡住，后来干脆把循环改成“先列后行”再跑，样例一次就过。

4.3 完整代码：四行输出一次搞定

第三问参考代码如下：

#include <bits/stdc++.h> using namespace std; int m, n; int castle[55][55]; int belong[55][55]; int area[2510]; int roomCnt = 0; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int wallBit[4] = {1, 2, 4, 8}; void dfs(int x, int y, int id) { belong[x][y] = id; area[id]++; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (belong[nx][ny] != 0) continue; if (castle[x][y] & wallBit[k]) continue; dfs(nx, ny, id); } } int main() { cin >> m >> n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> castle[i][j]; } } int maxArea = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (belong[i][j] == 0) { roomCnt++; area[roomCnt] = 0; dfs(i, j, roomCnt); maxArea = max(maxArea, area[roomCnt]); } } } int bestMerge = 0; int bestX = 0, bestY = 0; char bestDir = 'N'; for (int j = 0; j < n; j++) { for (int i = m - 1; i >= 0; i--) { // 检查北墙：当前格子与上方格子之间的墙 if (i - 1 >= 0) { int a = belong[i][j]; int b = belong[i - 1][j]; if (a != b) { int mergeArea = area[a] + area[b]; if (mergeArea > bestMerge) { bestMerge = mergeArea; bestX = i; bestY = j; bestDir = 'N'; } } } // 检查东墙：当前格子与右侧格子之间的墙 if (j + 1 < n) { int a = belong[i][j]; int b = belong[i][j + 1]; if (a != b) { int mergeArea = area[a] + area[b]; if (mergeArea > bestMerge) { bestMerge = mergeArea; bestX = i; bestY = j; bestDir = 'E'; } } } } } cout << roomCnt << "\n"; cout << maxArea << "\n"; cout << bestMerge << "\n"; cout << bestX + 1 << " " << bestY + 1 << " " << bestDir << "\n"; return 0; }

注意最后输出行和列时都加了 1，因为代码里我用的是从 0 开始的下标，而题目输出要求从 1 开始。这个细节很多人容易漏，样例输出看起来是两个数字，结果自己输出的是从 0 开始的下标，样例都过不了。

5. 踩坑记录：一份 WA 血泪史

5.1 常见错误表格

我把自己刷题时遇到的情况和群里别人问过的坑整理成一张速查表，如果你提交一直 WA，可以逐条对：

5.2 我印象最深的一个反例

我第二次 WA 是这样的：觉得只要从左上角往右下角遍历，然后不断用>=更新答案，不就能保证最西最南了吗？其实不行。

举个例子，假设有两个候选墙，一个在第 2 行第 1 列，一个在第 4 行第 2 列，它们合并面积相同。按优先级，第 2 行第 1 列因为列号小（第 1 列），应该胜出。但如果你按“行优先、从上到下”扫描，你会先扫到第 2 行第 1 列这个候选，然后又扫到第 4 行第 2 列这个候选，如果使用>=，后面的会把前面的覆盖掉，最后错误地输出第 4 行第 2 列。

所以要么循环顺序满足优先级，要么在更新时写成：

if (mergeArea > bestMerge) { bestMerge = mergeArea; ... }

只有当合并面积严格更大时才更新，平局一律保留之前的答案。这样配合正确的扫描顺序，优先级就天然成立了。

5.3 方向数组和墙位对应关系一定要反复确认

我在一开始写 DFS 时，方向数组用的顺序是“东、南、西、北”，结果wallBit对应的还是“西、北、东、南”，等于墙位和位移方向完全错位。这种错一般不会让你直接数组越界，而是会让房间里多走或者少走一些格子，导致房间数不对。

后来我把方向和墙位写成了这样，每次都是对照着看：

// k = 0 西 // k = 1 北 // k = 2 东 // k = 3 南 int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int wallBit[4] = {1, 2, 4, 8};

这样dx[k]、dy[k]和wallBit[k]一一对应，代码读起来也不容易乱。

6. 从这题还能学到什么

6.1 遇到“输出规则复杂”的题怎么处理

The Castle 这类题最值得学的，不是 Flood Fill 本身，而是处理复杂输出规则的方法。我的习惯是：先把题目的优先级用中文/伪代码写出来，再翻译成循环顺序。

这道题的优先级是：

最靠西(列小) > 最靠南(行大) > N > E

翻译成循环就是：

列从小到大 行从大到小 先检查 N 再检查 E

一旦写出这个对应关系，代码就很简单。如果嘴巴上说“从左上角扫”，最后代码和优先级对不上，那调试成本就大了。

这个思路对很多题目都适用，比如一些棋盘题、矩阵题要求“字典序最小路径”“按某种规则输出方案”，本质上都是把排序规则转换成遍历顺序或比较逻辑。把规则先写清楚，再动笔写代码，能省一半时间。

6.2 位掩码思想可以延伸到很多题目

这道题用整数表示墙，本质上是状态压缩。信息学竞赛里，状态压缩最常见的场景是：

• 迷宫中记录某个格子的开关状态；
• 图论中记录经过哪些点的状态（如旅行商问题的状压 DP）；
• 棋盘覆盖问题中用二进制表示某一行哪些位置被占用；
• 游戏地图中表示一个格子的四个方向是否可通行。

所以这道题虽然是个朴素搜索，但位运算部分并不朴素。如果你之前不太熟悉&、|、<<这些运算，不妨在 The Castle 上多练一练，自己手动把几个数字拆成二进制，再和地图对照，很快就能建立直觉。

6.3 从 1250 说开去

一本通里的 1250 对应的是 POJ 1164 这类经典题，原题甚至能追溯到早年国际信息学奥林匹克竞赛的题目。这类“老题”的好处是数据范围不大、边界条件清晰、套路固定，非常适合拿来练搜索和位运算的基本功。不要因为它古老就小看它，很多变体题其实就是在这个基础上加了“输出方案”“优先级排序”之类的限制。

如果这题你做明白了，还可以顺手试试这些变体：

• 把 Flood Fill 改成用并查集实现，看看怎么维护每个连通块面积；
• 把问题改成“拆两面墙能得到的最大房间面积”；
• 把地图改成二维字符迷宫，再用 BFS 求最短路径。

本质上都是在同一个二维网格上做连通性分析，只是转移条件和统计目标变了。

最后分享一个小经验：刷这种“看似模拟、实则搜索”的题，最忌讳一上来就抄模板。先把题目样例手工推一遍，理解每个数字的墙位，再把输出优先级写在草稿纸上，最后才写代码。The Castle 这题我之所以说它狠，不是算法难，而是细节多。只要把细节处理干净，它其实是一道非常棒的练手题，做完之后你对 Flood Fill、位运算、以及“如何把输出规则翻译成代码”都会有更深的体感。