AcWing 1359. 洛谷P1457 城堡

解题思路

\(\qquad\)这道题目是需要维护各种连通块信息的，所以这里我们可以也用并查集维护。这题我们如果注意一点细节，也是可以让代码变得很简洁的：

\(\qquad\quad 1.\)这道题的输入自带状态压缩，如果一个数\(a \& 1=1\)，那么这个数代表这个格子有西面的墙，东南北也是相似。

\(\qquad\quad 2.\)当移除方法不唯一时，优先选择对应方格区域更靠西的墙
\(\qquad\qquad\)如果仍存在多解，选择对应方格区域更靠南的墙。
\(\qquad\qquad\)在此基础上，还存在多解,那么优先选择北面的墙。
$\qquad\quad\ \ \ $这就启发着我们对于移除的时候优先从西面枚举，再枚举南面，由于格子都是黏在一起的（某个格子的南墙是它下面那个格子的北墙）所以我们只需要枚举北面和东面（因为条件3对北面有限制）的墙就可以了。

可爱的并查集

初始化不可以把存连通块大小的数组\(memset\)成1，因为是按照字节赋值的

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, M = N * N;
int p[M], n, m, g[N][N], sz[M];

int find(int x) 
{
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int main() 
{
    scanf("%d%d", &m, &n);
    
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
            scanf("%d", &g[i][j]);
            
    for (int i = 0; i < n * m; i ++ ) p[i] = i, sz[i] = 1;
    
    int cnt = n * m, max_area = 1; 
    int dx[] = {-1, 0}, dy[] = {0, 1}, dw[] = {2, 4};
    
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ ) 
            for (int k = 0; k < 2; k ++ ) 
            {
                if (g[i][j] & dw[k]) continue ;
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x >= n || y < 0 || y >= m) continue ;
                
                int u = i * m + j, v = x * m + y;
                u = find(u), v = find(v);
                if (u != v) {
                    p[u] = v, sz[v] += sz[u];
                    -- cnt, max_area = max(max_area, sz[v]);
                }
            }
            
    printf("%d\n%d\n", cnt, max_area);
    
    max_area = 0;
    int rx, ry, rw;
    for (int j = 0; j < m; j ++ ) 
        for (int i = n - 1; ~i; i -- ) 
            for (int k = 0; k < 2; k ++ ) 
            {
                if (!g[i][j] & dw[k]) continue ;
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x >= n || y < 0 || y >= m) continue ;
                
                int u = i * m + j, v = x * m + y;
                u = find(u), v = find(v);
                if (u != v) {
                    int ar = sz[v] + sz[u];
                    if (ar > max_area) max_area = ar, rx = i + 1, ry = j + 1, rw = k;
                }
            }
            
    printf("%d\n%d %d %c\n", max_area, rx, ry, (rw ? 'E' : 'N'));
    
    return 0;
}