P1457 [IOI 1994 / USACO2.1] 城堡 The Castle

思路

将每个格子看作一个点，没有墙的相邻格子属于同一个房间。

很明显这是一道求联通块的搜索题。

用 $cnt$ 表示当前连通块的编号，再 DFS 求出所有房间：

• co[i][j]：当前格子所属连通块编号
• sz[cnt]：该连通块面积

同时记录最大房间面积。

这里我们发现黑心出题人为了难为我们，没有直接告诉我们这个房间周围的墙。

但学过位运算的都知道 x & (1 << (i - 1)) 可以取到 $x$ 在二进制下第 $i$ 位上的数，算是一个状态压缩的小知识了。

而代表墙的加数正好都是 2 的正整数次幂！即二进制都可以表示为 100... 的形式，所以就可以用上述方法快速得到有没有墙。

接下来考虑拆墙。

拆掉一面墙后，只会连接两个原本不同的连通块，所以新连通块面积为：

由于一面墙会被两边格子重复记录，因此只枚举东墙和北墙即可。

这里还要注意一下枚举顺序：

1. 因为先选靠西的，所以第一层倒序枚举 $j$
2. 再选最靠南的，所以第二层正序枚举 $i$

大概就是这样：

for (int j = m;j >= 1;j--) {
    for (int i = 1;i <= n;i++) {
        //......
    }
}

接下来处理每个房间：

• 如果有东墙，尝试合并右边房间；
• 如果有北墙，尝试合并上方房间。

复杂度

DFS：$O(nm)$。

枚举墙：$O(nm)$。

总复杂度：$O(nm)$。

Code

#include<bits/stdc++.h>
using namespace std;
int n, m, maxsz, ans;
int a[100][100];
int co[100][100], sz[3000], cnt;
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
void dfs(int x, int y, int cnt) {
    co[x][y] = cnt, sz[cnt]++;
    for (int i = 0;i < 4;i++) {
        int u = x + dx[i], v = y + dy[i];
        if (u < 1 || v < 1 || u > n || v > m || co[u][v]) continue;
        if (a[x][y] & (1 << i)) continue;
        dfs(u, v, cnt);
    }
}
int main() {
    cin >> m >> n;//小心有坑！
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            cin >> a[i][j];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (!co[i][j]) {
                dfs(i, j, ++cnt);
                maxsz = max(maxsz, sz[cnt]);
            }
        }
    }
    cout << cnt << '\n' << maxsz << '\n';
    int x, y, z;
    for (int j = m;j >= 1;j--) {
        for (int i = 1;i <= n;i++) {
            if ((a[i][j] & 4) && co[i][j] != co[i][j + 1]) {
                int sum = sz[co[i][j]] + sz[co[i][j + 1]];
                if (ans <= sum) {
                    ans = sum;
                    x = i, y = j, z = 1;
                }
            }
            if ((a[i][j] & 2) && co[i][j] != co[i - 1][j]) {
                int sum = sz[co[i][j]] + sz[co[i - 1][j]];
                if (ans <= sum) {
                    ans = sum;
                    x = i, y = j, z = 0;
                }
            }

        }
    }
    cout << ans << '\n';
    if (z) printf("%d %d E", x, y);
    else printf("%d %d N", x, y);
    return 0;
}