最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界微资讯！AcWing 1359. 洛谷P1457 城堡

来源：博客园


(相关资料图)

解题思路

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

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

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

可爱的并查集

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

代码

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

关键词： 优先选择 在此基础上 在一起的