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输入 #17 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输出 #15 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连通分量标记、无重复枚举内部墙、优先级顺序遍历找最优解。效率保障线性遍历网格无嵌套高复杂度运算运行速度极快。代码简要说明全局变量定义mp[i][j][k]存储第i行j列格子第k个方向是否有墙1~4分别对应西、北、东、南。b[i][j]标记每个格子所属的房间编号。a[s]存储第s个房间的面积大小。dx、dy四个方向的坐标偏移量对应西、北、东、南。s房间总数ans记录最大面积。DFS连通函数标记当前格子所属房间遍历四个方向若该方向无墙且相邻格子未被访问则递归进入相邻格子累加房间面积。墙体解码对每个格子的编码数字依次对2取模判断最低位是否为1对应西、北、东、南四个方向是否有墙每判断一位右移一位除以2。房间划分与统计双重循环遍历所有格子遇到未标记房间的格子则新建房间启动DFS计算面积遍历完成后输出房间总数再遍历所有房间面积得到最大房间面积并输出。拆墙最大面积计算遍历每个格子的东墙与南墙若存在墙且两侧房间不同则计算合并面积更新全局最大拆墙面积并输出。最优拆墙位置查找按「列从小到大、行从大到小、先北墙后东墙」的优先级顺序遍历找到第一个符合最大合并面积的墙输出对应行号、列号与方向N/E直接结束程序保证优先级正确。输入输出优化使用scanf/printf保证读写效率适配题目数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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 k1;k4;k)if(mp[i][j][k]0b[idx[k-1]][jdy[k-1]]0){a[s];dfs(idx[k-1],jdy[k-1]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,m,n);for(ll i1;in;i)for(ll j1;jm;j){scanf(%lld,d);if(d%21)mp[i][j][1]1;d/2;if(d%21)mp[i][j][2]1;d/2;if(d%21)mp[i][j][3]1;d/2;if(d%21)mp[i][j][4]1;}for(ll i1;in;i)for(ll j1;jm;j)if(b[i][j]0){s;a[s]1;dfs(i,j);}printf(%lld\n,s);for(ll i1;is;i)ansmax(ans,a[i]);printf(%lld\n,ans);ans0;for(ll i1;in;i)for(ll j1;jm;j)for(ll k3;k4;k)if(mp[i][j][k]1b[i][j]!b[idx[k-1]][jdy[k-1]])ansmax(ans,a[b[i][j]]a[b[idx[k-1]][jdy[k-1]]]);printf(%lld\n,ans);for(ll j1;jm;j)for(ll k2;k3;k)for(ll in;i1;i--)if(mp[i][j][k]1b[i][j]!b[idx[k-1]][jdy[k-1]]a[b[i][j]]a[b[idx[k-1]][jdy[k-1]]]ans){printf(%lld %lld ,i,j);if(k3)printf(E\n);if(k2)printf(N\n);return0;}return0;}