P1457 城堡 The Castle

网页链接

P1457 城堡 The Castle

题目背景

我们憨厚的 USACO 主人公农夫约翰（Farmer John）以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡！

题目描述

喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。

另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。 你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。

城堡的平面图被划分成n × m n \times mn×m个正方形的单位，一个这样的单位可以有 $0 \sim 4 $ 面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。）

请仔细研究下面这个有注解的城堡平面图：

1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # -># | | | | # # #############################

• # \verb!#!#表示墙壁；
• | \verb!|!|和- \verb!-!-表示没有墙壁；
• -> \verb!->!->指向了一面墙，移除了这面墙我们就有一间最大的新房间。

友情提示，这个城堡的平面图是4 × 7 4 \times 74×7个单位的。一个“房间”的是平面图中一个由#、-、|围成的格子（就是图里面的那一个个的格子）。比如说这个样例就有5 55个房间。（大小分别为9 , 7 , 3 , 1 , 8 9,7,3,1,89,7,3,1,8个单位（排名不分先后））

移去箭头所指的那面墙，可以使2 22个房间合为一个新房间，且比移去其他墙所形成的房间都大。

城堡保证至少有2 22个房间，而且一定有一面墙可以被移走。

输入格式

第一行两个正整数m , n m,nm,n，表示城堡有n nn行m mm列。

每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数中的任意个加起来的。

1 11: 在西面有墙

2 22: 在北面有墙

4 44: 在东面有墙

8 88: 在南面有墙

城堡内部的墙会被规定两次。比如说( 1 , 1 ) (1,1)(1,1)南面的墙，亦会被标记为( 2 , 1 ) (2,1)(2,1)北面的墙。

输出格式

输出包含如下四行:

第一行：城堡的房间数目。

第二行：最大的房间的大小

第三行：移除一面墙能得到的最大的房间的大小

第四行：移除哪面墙可以得到面积最大的新房间。

选择最佳的墙来推倒。有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。

用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（N（北）或者E（东））。

输入输出样例 #1

输入 #1

7 4 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13

输出 #1

5 9 16 4 1 E

说明/提示

【数据范围】
对于100 % 100\%100%的数据，1 ≤ n , m ≤ 50 1\le n,m \le 501≤n,m≤50。

USACO 2.1

翻译来自 NOCOW。

解题思路

本题是经典的Flood Fill（洪水填充）+ 枚举拆墙的网格图问题，通过深度优先搜索划分连通房间，再枚举所有内部墙计算拆墙后的最大面积，最后按优先级筛选最优拆墙位置。

1. 墙信息解码

每个格子的墙体状态由一个整数编码，四位二进制分别对应西(1)、北(2)、东(4)、南(8)方向是否有墙。通过逐位取模的方式解码，将每个方向的墙体状态存入三维数组，方便后续遍历判断。

2. 连通分量划分（Flood Fill）

每个房间对应网格中的一个连通分量，只能通过无墙的方向通行。使用深度优先搜索（DFS）遍历所有格子：

• 遍历每个格子，若未被标记房间编号，则开启一个新房间。
• 从该格子出发，向四个无墙的方向递归扩展，标记所有连通格子为同一房间，并累计房间面积。
• 同时统计房间总数，记录每个房间的面积。

3. 计算拆单墙的最大房间面积

内部的每面墙为两个相邻格子共有，为避免重复枚举，只需遍历每个格子的东墙和南墙即可覆盖所有内部墙：

• 若当前方向存在墙，且墙两侧的格子属于不同房间，则拆掉这面墙后新房间面积为两个房间的面积之和。
• 枚举所有符合条件的墙，记录最大的合并面积。

4. 按优先级确定拆墙位置

题目规定多解时的优先级：最靠西（列号最小）> 同列最靠南（行号最大）> 同一格子北墙优先于东墙。
因此按以下顺序遍历：

• 列号从小到大（保证最西优先）；
• 每列中行号从大到小（保证最南优先）；
• 每个格子先检查北墙，再检查东墙（保证北墙优先）。
  第一个满足「墙存在、两侧不同房间、合并面积等于最大值」的墙，即为最优解，直接输出即可。

算法总时间复杂度为O ( n × m ) O(n \times m)O(n×m)，完全适配50×50的数据规模。

总结

核心逻辑：通过DFS洪水填充划分连通房间并统计面积，枚举所有内部墙计算合并后的最大面积，按题目指定的优先级顺序遍历找到最优拆墙位置。
关键操作：二进制墙体解码、DFS连通分量标记、无重复枚举内部墙、优先级顺序遍历找最优解。
效率保障：线性遍历网格，无嵌套高复杂度运算，运行速度极快。

代码简要说明

1. 全局变量定义：

   • mp[i][j][k]：存储第i行j列格子第k个方向是否有墙，1~4分别对应西、北、东、南。
   • b[i][j]：标记每个格子所属的房间编号。
   • a[s]：存储第s个房间的面积大小。
   • dx、dy：四个方向的坐标偏移量，对应西、北、东、南。
   • s：房间总数，ans：记录最大面积。

2. DFS连通函数：
   标记当前格子所属房间，遍历四个方向；若该方向无墙且相邻格子未被访问，则递归进入相邻格子，累加房间面积。

3. 墙体解码：
   对每个格子的编码数字，依次对2取模判断最低位是否为1，对应西、北、东、南四个方向是否有墙，每判断一位右移一位（除以2）。

4. 房间划分与统计：
   双重循环遍历所有格子，遇到未标记房间的格子则新建房间，启动DFS计算面积；遍历完成后输出房间总数，再遍历所有房间面积得到最大房间面积并输出。

5. 拆墙最大面积计算：
   遍历每个格子的东墙与南墙，若存在墙且两侧房间不同，则计算合并面积，更新全局最大拆墙面积并输出。

6. 最优拆墙位置查找：
   按「列从小到大、行从大到小、先北墙后东墙」的优先级顺序遍历，找到第一个符合最大合并面积的墙，输出对应行号、列号与方向（N/E），直接结束程序保证优先级正确。

7. 输入输出优化：使用scanf/printf保证读写效率，适配题目数据规模。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m,mp[55][55][5],b[55][55],d,s,a[2505],ans;constll dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};voiddfs(ll i,ll j){b[i][j]=s;for(ll k=1;k<=4;k++)if(mp[i][j][k]==0&&b[i+dx[k-1]][j+dy[k-1]]==0){a[s]++;dfs(i+dx[k-1],j+dy[k-1]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld%lld",&m,&n);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){scanf("%lld",&d);if(d%2==1)mp[i][j][1]=1;d/=2;if(d%2==1)mp[i][j][2]=1;d/=2;if(d%2==1)mp[i][j][3]=1;d/=2;if(d%2==1)mp[i][j][4]=1;}for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)if(b[i][j]==0){s++;a[s]=1;dfs(i,j);}printf("%lld\n",s);for(ll i=1;i<=s;i++)ans=max(ans,a[i]);printf("%lld\n",ans);ans=0;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)for(ll k=3;k<=4;k++)if(mp[i][j][k]==1&&b[i][j]!=b[i+dx[k-1]][j+dy[k-1]])ans=max(ans,a[b[i][j]]+a[b[i+dx[k-1]][j+dy[k-1]]]);printf("%lld\n",ans);for(ll j=1;j<=m;j++)for(ll k=2;k<=3;k++)for(ll i=n;i>=1;i--)if(mp[i][j][k]==1&&b[i][j]!=b[i+dx[k-1]][j+dy[k-1]]&&a[b[i][j]]+a[b[i+dx[k-1]][j+dy[k-1]]]==ans){printf("%lld %lld ",i,j);if(k==3)printf("E\n");if(k==2)printf("N\n");return0;}return0;}