解题思路
\(\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;
}
标签:sz,1359,洛谷,area,int,max,P1457,++,qquad
From: https://www.cnblogs.com/StkOvflow/p/17017003.html