洛谷刷题记——T155813 The Castle

这是七道题中的第二道题。

题目描述

我在洛谷找到了这道题的原题,如果不想看我描述的话可以去洛谷看: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)是一种精致小巧的数据结构,它主要用于处理一些不相交集合的合并问题。

我也想说人话,但是并查集这个概念······我也讲不太清楚。我们举个栗子吧:

在武林世界中,有五位顶尖大侠:甲、乙、丙、丁、戊。下面用表格表示各位大侠的相互关系(下面是大侠名,上面是大侠遵从谁的管理),既然是大侠,那肯定得有大侠的风范,所以我们每位大侠都只服自己。

初始状态

现在,大侠甲和大侠乙打了一架,大侠甲输了,于是大侠甲不得不服从大侠乙,于是他们之间的关系变成了这样:

乙打赢甲

然后,大侠乙和大侠丙又打了一架,大侠丙赢了,于是关系变成了这样:

丙打赢乙

然后大侠丙又和大侠丁打了一架,大侠丁赢了,于是关系变成了这样:

丁打赢丙

现在大侠戊要和大侠甲打架。但是武林中有一个规矩:找大哥,如果咱大哥是一样的,那么按照江湖规矩,咱俩就得握手言和。大侠甲往上一找,大哥是大侠乙,然后大侠乙再往上一找,大哥是大侠丙······最终大侠甲的大哥是大侠丁,然后大侠戊的大哥就是自己,大哥不一样,那咱就打吧。现在有两种可能:

  • 大侠戊打输了

那么,顺理成章地,大侠甲就成为了大侠戊的大哥,他们之间的关系变为这样:

戊没打赢
  • 大侠戊打赢了

这种情况难办了,甲已经有一个大哥了,而按照江湖规矩,一个人是不能有两个大哥的。那怎么办呢?没关系,江湖规矩说了,你输了,就带着你的大哥一起当他小弟(丁:???)就好了。现在是最新的关系表:

戊打赢了

武林决战,乙和丙要决出冠军(假设丁和戊都打输了)。打架第一步:找大哥。这下可好,两人的大哥都是丁。按照江湖规矩,大哥一样就得握手言和。于是乙和丙停战了,快乐地手拉手做朋友╭(′▽`)╭(′▽`)╯

这就是并查集。并查集有两个操作:

  1. 合并“帮派”:把两个“帮派”合并在一起,变成一个帮派
  2. “找大哥”:找到当前“帮派”中的“领头人”

实现

简单实现

根据这两个操作,我们很容易就能编写出并查集的一段代码:

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;
}

写在最后

其实这道题不难理解,只是非常之繁琐,很容易被一些小细节坑到,做题时要仔细一些。

另外,我现在想到一种优化方法:我们可以使用一种简化版的并查集,即给每一个房间都编一个号,然后给每个点的号设为所属的房间号,只用在房间号下记录房间大小,这样做会比用并查集还要快,而且更为简单。这也是给我自己一个教训。

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

返回顶部
京ICP备15050995号