题解 P1457 【城堡 The Castle】

这题看上去很复杂，但实际上没有那么困难。 1. 因为这个图中有很多连通块，认为是房间：需要对同一个房间的 cell 做上标记，并且计算连通块的大小： 对每个未染色的单元 dfs 搜索染色就可以了。 这是基本操作。 2. 抽象化 “墙” 这个概念， 便于操作。有两种墙， 1. 一种是虚拟的抽象的概念：南北西东4个墙的标记和方向； 2. 另一种是实墙，可以评估其价值：拆除后可以变成的最大房间大小。 这题主要坑在最后一个地方： 对于一个实墙，如果拆除价值同样大，则选择 $y$ 大的或 $x$ 小的； 如果是同一个 cell（即 $x$ 和 $y$ 相同），则优先选择 `N` 墙，即北墙。 可以直接用结构体比较选择最大。注意写好比较函数就可以了。 还写了打印 castle 的函数，很好玩。 ```cpp #include <cstdio> const int MAX_N = 52; int n, m; int walls[MAX_N][MAX_N]; int mark[MAX_N][MAX_N] = {0}; // 染色 struct Wall { int dx, dy; // direction int c, mask; // char and bit mask Wall(int dx, int dy, int c, int mask): dx(dx), dy(dy), c(c), mask(mask) {} bool exist(int v) { return mask & v; } }; struct RealWall { int x, y; int c, value; RealWall() {} RealWall(int x, int y, int c, int value): x(x), y(y), c(c), value(value) {} }; bool cmp(RealWall &a, RealWall &b) { if (a.value != b.value) return a.value > b.value; if (a.y != b.y) return a.y < b.y; // farthest to the west if (a.x != b.x) return a.x > b.x; // farthest to the south // same module return a.c == 'N'; // a.c must be 'N' or 'E' } Wall wall[4] = { Wall(0, -1, 'W', 1 << 0), Wall(-1, 0, 'N', 1 << 1), Wall(0, 1, 'E', 1 << 2), Wall(1, 0, 'S', 1 << 3), }; bool WALL_W(int x) { return wall[0].exist(x); } bool WALL_N(int x) { return wall[1].exist(x); } bool WALL_E(int x) { return wall[2].exist(x); } // for Wall E bool WALL_S(int x) { return wall[3].exist(x); } void print_castle() { int i, j; for (i = 1; i <= m; ++i) { // print walls for (j = 1; j <= n; ++j) { if (WALL_N(walls[i][j])) printf("####"); else printf("# "); } printf("#\n"); // print through for (j = 1; j <= n; ++j) { if (WALL_W(walls[i][j])) printf("# "); else printf(" "); } printf("#\n"); } for (j = 1; j <= n; ++j) printf("####"); printf("#\n"); } int dfs(int x, int y, int color) { if (mark[x][y]) return 0; mark[x][y] = color; int count = 1; for (int i = 0; i < 4; ++i) if (!wall[i].exist(walls[x][y])) count += dfs(x + wall[i].dx, y + wall[i].dy, color); return count; } int main() { int i, j; scanf("%d %d", &n, &m); for (i = 1; i <= m; ++i) for (j = 1; j <= n; ++j) scanf("%d", &walls[i][j]); // print_castle(); int color = 1; int size[MAX_N * MAX_N] = {0}; for (i = 1; i <= m; ++i) for (j = 1; j <= n; ++j) if (!mark[i][j]) { size[color] = dfs(i, j, color); ++color; } int max_size = 0; for (i = 1; i < color; ++i) if (max_size < size[i]) max_size = size[i]; // printf("%d: %d\n", i, size[i]); // select max int c, nc; RealWall bestwall = RealWall(0, 0, 0, 0), current; for (i = m; i > 0; --i) for (j = 1; j <= n; ++j) { c = mark[i][j]; for (int k = 0; k < 4; ++k) { nc = mark[i + wall[k].dx][j + wall[k].dy]; if (wall[k].exist(walls[i][j]) && c != nc) { current = RealWall(i, j, wall[k].c, size[c] + size[nc]); if (cmp(current, bestwall)) bestwall = current; } } } printf("%d\n", color - 1); printf("%d\n", max_size); printf("%d\n", bestwall.value); printf("%d %d %c\n", bestwall.x, bestwall.y, bestwall.c); return 0; } ```