这是七道题中的第二道题。
文章目录
题目描述
我在洛谷找到了这道题的原题，如果不想看我描述的话可以去洛谷看：P1457 [USACO2.1]城堡 The Castle。
题目背景
取材自 USACO2.1
题目描述
如图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 \( m\times n \) 个方格区域，每个方格区域可以有0~4面墙。注意：墙体厚度忽略不计。
（作者注：“->”的意思为推掉这堵墙能够获得最大的房间）
输入格式
第一行包含两个整数 m 和 n，分别表示城堡东西方向的长度和南北方向的长度。
接下来 n 行，每行包含 m 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块 \( \left(1, 1\right) \) 的南墙同时也是方块 \( \left(2, 1\right) \) 的北墙。数据保证城堡至少有两个房间。
输出格式
共4行，前2行分别为房间总数和最大房间的面积（方块数）。
第 3 行：移除一面墙能得到的最大的房间大小
第 4 行：移除哪面墙。 选择最佳的墙来推倒。有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。
用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（“N”（北）或者“E”（东））。
输入输出样例
输入 #1
7 4 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
输出 #1
5 9 16 4 1 E
说明/提示
\( 1\leq m, n\leq 50, 0\leq P\leq 15 \)
知识链接
DFS染色
DFS染色是DFS的一种特殊应用。DFS是与BFS相对的一种搜索方式，在后面会仔细讨论，这里知道大概是一种搜索方式就好了。DFS染色用于解决这类“房间问题”，包括问你有几个房间、最大的房间有多大、最小的房间有多大等等类似的问题。
具体做法为：从一个点开始DFS，把访问过的点染上色，碰到墙壁就停止，然后从其他点继续进行染色，直到无法再染色为止。DFS染色可以用以下的模型来进行理解：把房间看成一个个空水池，给第一个水池蓄水，蓄满水后给第二个水池蓄水······最后，给多少个水池蓄水了就有多少个房间，而最大的房间就是放水最多的水池。下面是一个示例代码：
...
#include <algorithm>
...
const int kMaxN(50);
const int kMaxM(50);
...
bool kIsVis[kMaxN + 5][kMaxM + 5]; // 记录染色
int kXMov[5] = {0, -1, 0, 1}; // 坐标移动
int kYMov[5] = {1, 0, -1, 0};
...
int Dfs(int, int, int, int); // DFS染色主程序，返回当前水池大小
inline bool IsValid(int, int, int, int); // 判断坐标是否合法或撞墙，具体情况具体实现
...
int main(void) {
...
int room_num(0), max_size(0); // room_num是水池个数，max_size是最大水池大小
...
// 要从每个点都放水试试
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!kIsVis[i][j]) { // 如果当前点没有染过色，说明这是一个新的蓄水池
++room_num;
max_size = max(max_size, Dfs(n, m, i, j)); // 更新最大的蓄水池大小
}
}
}
...
return 0;
}
...
int Dfs(int n, int m, int x, int y) {
if (kIsVis[x][y]) // 如果当前点已经染过色了
return 0; // 直接退出
int res(1); // res是从当前开始能染色的格子数。当前点肯定能染色，所以初始化为1
kIsVis[x][y] = true; // 染色
for (int i = 0; i < 4; ++i) {
int dx(x + kXMov[i]), dy(y + kYMov[i]); // 新坐标
if (IsValid(n, m, dx, dy)) // 如果新坐标合法（没越界，没撞墙）
res += Dfs(n, m, dx, dy); // 去新坐标染色
}
return res;
}
...
inline bool IsValid(int n, int m, int dx, int dy) {
// 按题目要求实现
...
}
...
大家其实已经发现了，染色不一定非要用DFS实现，用BFS也是可以的，只不过DFS通常比较简便，所以我们一般用DFS进行染色，而不是BFS，大家可以试试用BFS实现染色。
并查集
概念
并查集（Disjoint Set）是一种精致小巧的数据结构，它主要用于处理一些不相交集合的合并问题。
我也想说人话，但是并查集这个概念······我也讲不太清楚。我们举个栗子吧：
在武林世界中，有五位顶尖大侠：甲、乙、丙、丁、戊。下面用表格表示各位大侠的相互关系（下面是大侠名，上面是大侠遵从谁的管理），既然是大侠，那肯定得有大侠的风范，所以我们每位大侠都只服自己。
| 甲 | 乙 | 丙 | 丁 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
现在，大侠甲和大侠乙打了一架，大侠甲输了，于是大侠甲不得不服从大侠乙，于是他们之间的关系变成了这样：
| 乙 | 乙 | 丙 | 丁 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
然后，大侠乙和大侠丙又打了一架，大侠丙赢了，于是关系变成了这样：
| 乙 | 丙 | 丙 | 丁 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
然后大侠丙又和大侠丁打了一架，大侠丁赢了，于是关系变成了这样：
| 乙 | 丙 | 丁 | 丁 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
现在大侠戊要和大侠甲打架。但是武林中有一个规矩：找大哥，如果咱大哥是一样的，那么按照江湖规矩，咱俩就得握手言和。大侠甲往上一找，大哥是大侠乙，然后大侠乙再往上一找，大哥是大侠丙······最终大侠甲的大哥是大侠丁，然后大侠戊的大哥就是自己，大哥不一样，那咱就打吧。现在有两种可能：
- 大侠戊打输了
那么，顺理成章地，大侠甲就成为了大侠戊的大哥，他们之间的关系变为这样：
| 乙 | 丙 | 丁 | 丁 | 甲 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
- 大侠戊打赢了
这种情况难办了，甲已经有一个大哥了，而按照江湖规矩，一个人是不能有两个大哥的。那怎么办呢？没关系，江湖规矩说了，你输了，就带着你的大哥一起当他小弟（丁：？？？）就好了。现在是最新的关系表：
| 乙 | 丙 | 丁 | 戊 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
武林决战，乙和丙要决出冠军（假设丁和戊都打输了）。打架第一步：找大哥。这下可好，两人的大哥都是丁。按照江湖规矩，大哥一样就得握手言和。于是乙和丙停战了，快乐地手拉手做朋友╭(′▽`)╭(′▽`)╯
这就是并查集。并查集有两个操作：
- 合并“帮派”：把两个“帮派”合并在一起，变成一个帮派
- “找大哥”：找到当前“帮派”中的“领头人”
实现
简单实现
根据这两个操作，我们很容易就能编写出并查集的一段代码：
int kDisSet[kMaxN + 5];
// 初始化并查集
void InitSet(void) {
for (int i = 0; i < kMaxN; ++i)
kDisSet[i] = i; // 初始情况下，每位大侠都是自己的“大哥”
}
// 合并“帮派”
void UnionSet(int x, int y) {
int a(FindSet(x)), b(FindSet(y)); // 找两人的大哥
if (a != b) // 如果大哥不一样
kDisSet[a] = b; // 合并
}
// 找大哥（递归版）
int FindSet(int x) {
// 首先找自己的直系大哥
// 如果自己的直系大哥没有大哥，那就是帮派领头人了
// 如果自己的直系大哥有大哥，那就去找直系大哥的大哥，这样递归进行
return x == kDisSet[x] ? x : FindSet(kDisSet[x]);
}
优化
合并优化
以戊打赢的情况为例子，我们合并有两种情况：把丁合并到戊底下，或把戊合并到甲底下。可以看出来，相比于丁的“拖家带口”挪位置，戊这个“单身汉”挪位置显然能够减少并查集的层数，增加查询速度。为了实现这个操作，我们需要一个数组 height[n] 来记录每个集的层数。以下是优化版的合并操作：
int kDisSet[kMaxN + 5];
int kHeight[kMaxN + 5];
// 初始化并查集
void InitSet(void) {
memset(kHeight, 0, sizeof(kHeight)); // 初始情况下，每个集的高度都为0
for (int i = 0; i < kMaxN; ++i)
kDisSet[i] = i; // 初始情况下，每位大侠都是自己的“大哥”
}
// 合并“帮派”优化版
void UnionSet(int x, int y) {
int a(FindSet(x)), b(FindSet(y)); // 找两人的大哥
if (kHeight[a] == kHeight[b]) { // 如果两个集高度一样
++kHeight[a]; // 把b合并到a上，a的高度＋1
kDisSet[b] = a;
} else { // 把矮树合并到高树上
if (kHeight[a] < kHeight[b])
kDisSet[a] = b;
else
kDisSet[b] = a;
}
}
路径压缩
在上面戊打赢的例子中，如果甲要找大哥的话，必须先找到乙，再找到丙······最后找到戊，这是一个非常慢的操作，复杂度可以高达 \( O\left(n\right) \)，完全体现不出并查集的优势来。通过分析可知，并查集的操作中并不需要知道每个帮派中每一层的上下级关系，并查集只需要知道两个信息：
- 这个点属于哪个集
- 这个集的大哥是谁
所以我们就有了一个优化的大杀器——“路径压缩”。路径压缩是什么意思呢？就是所有人都直接跟大哥说话，直接连到大哥。经过路径压缩后，新的人际关系变成这样了：
| 戊 | 戊 | 戊 | 戊 | 戊 |
| 甲 | 乙 | 丙 | 丁 | 戊 |
这样子，甲要找大哥只需要找一层就能找到了，也就是 \( O\left(1\right) \) 的常数时间，是非常快的。
// 查找路径＋路径压缩
int FindSet(int x) {
if (x != kDisSet[x])
kDisSet[x] = FindSet(kDisSet[x]); // 将当前点的直系大哥设为领头人
return kDisSet[x];
}
【可选】查找递归优化
这个优化用于数据规模特别大、递归会爆栈的情况下。优化思想：用while循环模拟递归查找。这里就不多讲解了，很简单的代码。
// 查找路径（递归优化）＋路径压缩
int FindSet(int x) {
int root(x);
while (kDisSet[root] != root) // 查找大哥
root = kDisSet[root];
// 以下为路径压缩
int i(x), j(0);
while (i != root) {
j = kDisSet[i]
kDisSet[i] = root;
i = j;
}
return root; // 返回大哥
}
其实在平常状况下也可以用这个优化，毕竟递归总是比较慢的。
解题思路
本题要求较为繁琐，可以分为三部分解决：第一部分解决存图问题，第二部分解决有多少房间和最大房间大小的问题，第三部分解决去墙问题。
第一部分：存图
这道题非常之ex，不像其他类型题目那样墙体也占一格，而是四面的墙合并到一个方格内。如果单单存方格的话，我们用一个 \( n\times m \) 的二维数组存就好了。那么墙怎么存呢？很简单，只要再开一维就好了：
bool kCastle[kMaxN + 5][kMaxM + 5][5];
因为只需要记录是否有墙体，所以用bool数组就行。为了方便，我们规定0代表西边，1代表北边，2代表东边，3代表南边。
储存的问题解决了，那我们该如何读取墙呢？我们先来观察一下题目中的四个数：1, 2, 4, 8，怎么样，有没有发现什么？没错，这些数都是2的整数次幂。一提到这个，我们第一时间肯定想到的是二进制：一个数如果由n个2的整数次幂且不重复的数相加，那么如果这个数的第m位为1，则相加的数中肯定有 \( 2^m \)。至于如何判断某一位是否为1，我们可以使用按位与运算。
// x和y是当前格子坐标，wall_num是读入的数字
inline void AddWall(int x, int y, int wall_num) {
if (wall_num & 1) // 如果加数中有1
kCastle[x][y][0] = true; // 西边有墙
if (wall_num & 2) // 若加数中有2
kCastle[x][y][1] = true; // 北边有墙
if (wall_num & 4) // 若加数中有4
kCastle[x][y][2] = true; // 东边有墙
if (wall_num & 8) // 若加数中有8
kCastle[x][y][3] = true; // 南边有墙
}
第二部分：房间问题
这部分问题非常之简单，就是上面所讲的DFS染色的模板题。然而，怎么判断墙体呢？只要确定去的这个方向是否有墙就行了。那么往西走的坐标变化是什么呢？上北下南左西右东，往西走就相当于向左走，那坐标变化就是 \( \left(x – 1, y\right) \) 了······错！仔细观察：在图中往西走是往左走不差，但观察坐标变化，你可以发现图中的坐标系和咱们存图的坐标系是反的！也就是说，往西走的坐标变化是 \( \left(x, y – 1\right) \)，其他三个方向以此类推，这也是一个坑点了。剩下的在后面的代码中会有注释描述。
第三部分：去墙部分（难点）
这部分是本题中最难的点，需要用枚举实现，且实现起来非常麻烦。先简化一下模型：一个方格只用枚举两堵墙，因为另外两堵墙肯定被其他方格枚举过了，按照题意要求我们要枚举北边和东边两堵墙，且北边的墙要先于东边枚举。这样我们可以将问题分为两部分解决：找每个房间的大小，和枚举每堵墙。
房间大小
这个问题乍一看很简单，实际很难实现。首先考虑用一个二维数组记录每个点所属的房间大小，在染色时更新，但发现无法在染色途中更新大小，再DFS一次又麻烦又慢，放弃此做法。
这时我灵机一动：这不是并查集嘛！
你可能会问：“这怎么就并查集了？”你想想啊，将某个点能到达的点都加入到一个集里，那么就只在这个点上记录房间大小不就好了？如果想要获得某个点所属的房间大小，找到大哥，然后就可以获得房间大小了，多方便啊！
那么，像这样的二维点该怎么使用并查集呢？有两种方法：一、使用二维的并查集；二、将二维点坐标转为一维。第一种方法非常之麻烦，我们采用第二种方法。但如何将二维点坐标转为一维呢？
我们先脑补一个方阵（懒得画图了），有n行m列，是一个 \( n\times m \) 的矩阵，坐标从0开始，即0~n-1和0~m-1。然后，给每个格子都编个号：从 \( 0 \) 开始，横着来，逐个递增，最终编到右下角的点，编号应该是 \( n\times m – 1 \)。我们看到，这其实也是一种特殊的哈希函数，因为每一个点都有且只有一个对应的编号数字，而且这个哈希函数非常优秀，不可能发生碰撞，因为一个数字编号肯定也只对应一个点。由分析可知，我们可以得出一个简单的哈希函数：
$$ Hash\left(x, y\right) = x\cdot m + y $$
然后，我们改变一下策略：现在我们的坐标从1开始，即1~n和1~m，那么这时候的哈希函数又该如何变化呢？改变后的哈希函数如下：
$$ Hash\left(x, y\right) = \left(x – 1\right)\cdot m + y – 1 $$
为了编程简便，我们可以用以下这个式子：
$$ Hash\left(x, y\right) = \left(x – 1\right)\cdot m + y $$
这样子，数字编号就是从1开始的了。由此，我们对于所有点可以有哈希函数：
$$ Hash\left(x, y\right) = \left(x – p\right)\cdot m + y – p $$
其中 \( p \) 为坐标的起始点。由于我们的坐标是从1开始的，我们可以直接套用上面的那个简便的式子计算二维点的一维坐标，然后就可以愉快地使用并查集啦！
枚举墙
说是枚举墙，其实就是枚举方格，然后看它北边和东边有没有墙，如果有墙的话就把墙两边的房间大小加起来，更新最大房间大小就好了。那么题目中先选靠西的墙再选靠南的墙该怎么做呢？很简单，我们先从西开始遍历，然后再从南开始遍历就好了。从西开始遍历，也就是说y=1到m；从南开始遍历，也就是说x=n到1，非常简单。
代码展示
拒绝抄袭，共创和谐社会[机智]
#include <cstdio> // std::scanf, std::printf
#include <cstring> // std::memset
#include <algorithm> // std::max
using namespace std;
const int kMaxN(50);
const int kMaxM(50);
bool kCastle[kMaxN + 5][kMaxM + 5][5]; // 墙
bool kIsVis[kMaxN + 5][kMaxN + 5]; // 染色
int kXMov[5] = {0, -1, 0, 1}; // 横坐标变化：0是往西走，1是往北走，2是往东走，3是往南走
int kYMov[5] = {-1, 0, 1, 0}; // 纵坐标变化，同上
int kUfs[kMaxN * kMaxM + 5]; // 并查集，不用在意名称。注意数组大小是n×m
int kHeight[kMaxN * kMaxM + 5]; // 并查集合并优化：高度记录
int kSizes[kMaxN * kMaxM + 5]; // 记录每个房间的大小
inline void AddWall(int, int, int);
int Dfs(int, int, int, int); // DFS染色
inline bool IsValid(int, int, int, int, int, int, int); // 判断是否越界或撞墙
void UnionSet(int, int);
int FindSet(int);
int main(void) {
// room_num是房间个数，max_size是最大房间大小，new_max_size是去掉一堵墙能获得的最大的房间的大小，new_room_x是去掉的墙所属的方格的x坐标，new_room_y则是y坐标，dis_wall是被去掉的墙是北墙还是东墙
int m(0), n(0), room_num(0), max_size(0), new_max_size(0), new_room_x(0),
new_room_y(0), dis_wall(0);
memset(kCastle, 0, sizeof(kCastle));
memset(kIsVis, 0, sizeof(kIsVis));
memset(kHeight, 0, sizeof(kHeight));
memset(kSizes, 0, sizeof(kSizes));
scanf("%d %d", &m, &n);
for (int i = 1; i < n + 1; ++i) {
for (int j = 1; j < m + 1; ++j) {
int wall(0);
scanf("%d", &wall);
AddWall(i, j, wall); // 加墙
kUfs[(i - 1) * m + j] = (i - 1) * m + j; // 初始化并查集，省掉了一个InitSet函数
}
}
// DFS染色
for (int i = 1; i < n + 1; ++i) {
for (int j = 1; j < m + 1; ++j) {
if (!kIsVis[i][j]) {
int room_size(Dfs(n, m, i, j));
max_size = max(max_size, room_size); // 更新最大房间大小
kSizes[(i - 1) * m + j] = room_size; // 在并查集根节点记录房间大小
++room_num; // 房间数＋1
}
}
}
// 去墙
for (int i = 1; i < m + 1; ++i) { // 从西边开始枚举
for (int j = n; j > 0; --j) { // 再从南边开始枚举
for (int k = 1; k < 3; ++k) { // 枚举一个方格中北边和东边的墙，北边优先
if (kCastle[j][i][k]) { // 如果有墙
int dx(j + kXMov[k]), dy(i + kYMov[k]); // 获取墙那边的坐标
if (IsValid(n, m, j, i, dx, dy, 4)) { // 如果这个坐标合法
int old_pos(FindSet((j - 1) * m + i)), // 将这边的坐标转为一维，并找到大哥节点
new_pos(FindSet((dx - 1) * m + dy)), // 将那边的坐标转为一维，并找到大哥节点
new_size(kSizes[old_pos] + kSizes[new_pos]); // 将两边房间的大小相加
if (new_max_size < new_size && old_pos != new_pos) { // 如果新房间大小大于已知最大房间大小，且这个墙两边的点不在一个房间里
// 更新
new_max_size = new_size;
new_room_x = j;
new_room_y = i;
dis_wall = k;
}
}
}
}
}
}
printf("%d\n%d\n%d\n%d %d %c\n", room_num, max_size, new_max_size,
new_room_x, new_room_y, 1 == dis_wall ? 'N' : 'E'); // 输出
return 0;
}
int Dfs(int n, int m, int x, int y) {
if (kIsVis[x][y])
return 0;
int res(1);
kIsVis[x][y] = true;
for (int i = 0; i < 4; ++i) {
int dx(x + kXMov[i]), dy(y + kYMov[i]);
if (IsValid(n, m, x, y, dx, dy, i)) {
UnionSet((x - 1) * m + y, (dx - 1) * m + dy); // 将访问过的点加入并查集内
res += Dfs(n, m, dx, dy);
}
}
return res;
}
inline bool IsValid(int n, int m, int x, int y, int dx, int dy, int dir) {
if (0 < dx && dx < n + 1 && 0 < dy && dy < m + 1 && !kCastle[x][y][dir]) // 如果kCastle[x][y][dir]=false的话，代表这个方向没有墙，可以走
return true;
else
return false;
}
void UnionSet(int x, int y) {
int a(FindSet(x)), b(FindSet(y));
if (kHeight[a] == kHeight[b]) {
++kHeight[a];
kUfs[b] = a;
} else {
if (kHeight[a] < kHeight[b])
kUfs[a] = b;
else
kUfs[b] = a;
}
}
int FindSet(int x) {
int root(x);
while (kUfs[root] != root)
root = kUfs[root];
int tmp1(x), tmp2(0);
while (tmp1 != root) {
tmp2 = kUfs[tmp1];
kUfs[tmp1] = root;
tmp1 = tmp2;
}
return root;
}
inline void AddWall(int x, int y, int wall_num) {
if (wall_num & 1)
kCastle[x][y][0] = true;
if (wall_num & 2)
kCastle[x][y][1] = true;
if (wall_num & 4)
kCastle[x][y][2] = true;
if (wall_num & 8)
kCastle[x][y][3] = true;
}
写在最后
其实这道题不难理解，只是非常之繁琐，很容易被一些小细节坑到，做题时要仔细一些。
另外，我现在想到一种优化方法：我们可以使用一种简化版的并查集，即给每一个房间都编一个号，然后给每个点的号设为所属的房间号，只用在房间号下记录房间大小，这样做会比用并查集还要快，而且更为简单。这也是给我自己一个教训。