P1519 穿越栅栏 Overfencing 【洛谷算法习题】

P1519 穿越栅栏 Overfencing网页链接P1519 穿越栅栏 Overfencing题目描述Farmer John 在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是他所建造的迷宫是一个“完美的”迷宫即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽度W WW1 ≤ W ≤ 38 1 \leq W \leq 381≤W≤38及高度H HH1 ≤ H ≤ 100 1 \leq H \leq 1001≤H≤100。2 × H 1 2 \times H12×H1行每行2 × W 1 2 \times W12×W1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数即使从这一点以最优的方式走向最靠近的出口它仍然需要最多的步数。当然了牛们只会水平或垂直地在 X 或 Y 轴上移动他们从来不走对角线。每移动到一个新的方格算作一步包括移出迷宫的那一步。这是一个W 5 , H 3 W5,H3W5,H3的迷宫----- | | - - | | | | -- | | | - ---如上图的例子栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。输入格式第一行两个整数W , H W,HW,H。接下来2 × H 1 2 \times H12×H1行每行2 × W 1 2 \times W12×W1个字符描述一个迷宫。输出格式输出一个单独的整数表示最坏情况下牛走出迷宫的最小步数。输入输出样例 #1输入 #15 3 ----- | | - - | | | | -- | | | - ---输出 #19说明/提示翻译来自NOCOWUSACO 2.4解题思路本题是一个在字符迷宫中寻找最坏情况出口距离的搜索问题。核心在于将字符网格转化为可走的图然后以两个出口为起点进行多源 BFS求出每个格子到最近出口的最短距离最后取最大值并换算为实际步数。1. 问题等价转化迷宫表示给定W × H W \times HW×H的迷宫实际字符图为( 2 H 1 ) (2H1)(2H1)行、( 2 W 1 ) (2W1)(2W1)列。奇数行、奇数列是墙壁、-、|偶数行、偶数列是房间或通道。可走节点字符图中的空格 表示牛可以站立的格子。代码中把这些空格标记为vis[i][j]0表示可以通行。出口判定牛从迷宫边界上的空格走出迷宫。代码将位于网格边界第1行、最后一行、第1列、最后一列且是空格的格子视为出口记录其坐标并设初始距离为 1代表“移出迷宫的那一步”已计入。距离定义在字符网格中相邻可走空格之间的距离为 1。牛在迷宫中从一个房间移动到相邻房间在字符图上需要走两步例如从一个空格到隔壁空格中间隔着墙壁。因此在字符网格上计算出的最短路长度恰好是实际步数的 2 倍最终答案需除以 2。2. 算法实现多源 BFS建图与标记读入W , H W, HW,H后将其更新为字符图的真实宽高w 2*W1, h 2*H1。用getline按行读取迷宫对每行的每个字符判断若是空格则将vis[i][j]置为 0可走。如果该空格位于边界则将其记录为出口坐标存入ex[], ey[]同时初始化该点的dis 1。多源 BFS依次以每个出口为起点执行 BFS。使用队列queuendused数组控制访问去重每次 BFS 前清空。扩展四个方向如果邻居是未访问的可走节点更新其距离dis[nx][ny] min(dis[nx][ny], dis[cur.x][cur.y]1)并入队。两次 BFS 后dis数组即存储每个空格到最近出口的最短字符网格距离。答案提取遍历所有格子若dis[i][j]不为无穷大用其更新全局最大值ans。输出ans / 2即实际的最坏步数。3. 复杂度分析时间复杂度节点数上限约201 × 77 15477 201 \times 77 15477201×7715477每条边最多四个方向两次 BFS 总复杂度O ( W H ) O(WH)O(WH)完全可行。空间复杂度O ( W H ) O(WH)O(WH)存储距离与访问数组符合限制。总结通过将字符迷宫映射为网格图找出边界上的两个出口作为多源 BFS 起点计算出每个可走格子到出口的最短距离最大距离的一半即为从最糟糕点走出迷宫的最小步数。除以 2 的操作巧妙地将字符图上的两倍步长转化为实际移动步数。代码简要说明全局变量与方向数组dis[210][210]记录每个格子到最近出口的距离初始 INF。vis[210][210]1 表示墙0 表示可走的空格。used[210][210]单次 BFS 的访问标记。dx[], dy[]四个方向的移动增量。初始化init()先用cin.getline读取并丢弃输入缓冲中的换行符。循环h次读取迷宫行判断空格并标记vis[i][j]0。若空格在边界记录为出口设置dis[i][j]1。BFS 函数bfs(x, y)从出口(x,y)出发BFS 遍历所有连通的可走节点更新dis数组为更短距离。主函数逻辑读入W, H扩展为字符图尺寸。调用init()建图并寻找出口。对每个出口执行一次 BFS每次清空used。扫描全图求ans max(dis)输出ans/2。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll dx[]{1,-1,0,0};constll dy[]{0,0,1,-1};chars[500];ll w,h,ans,cnt,ex[2],ey[2];ll dis[210][210],vis[210][210];boolused[210][210];structnd{ll x,y;}now;queuendq;voidinit(){cin.getline(s,500);for(ll i0;i210;i){fill(dis[i],dis[i]210,INF);fill(vis[i],vis[i]210,1);}for(ll i1;ih;i){cin.getline(s,500);for(ll j1;jw;j)if(s[j-1] ){vis[i][j]0;if((i1||j1||ih||jw)vis[i][j]0){ex[cnt]i;ey[cnt]j;dis[i][j]1;cnt;}}}}voidbfs(ll x,ll y){nd st;st.xx;st.yy;q.push(st);used[x][y]1;while(!q.empty()){nd curq.front();q.pop();for(ll i0;i4;i){ll nxcur.xdx[i],nycur.ydy[i];if(nx0nxhny0nywvis[nx][ny]0used[nx][ny]0){used[nx][ny]1;dis[nx][ny]min(dis[nx][ny],dis[cur.x][cur.y]1);now.xnx;now.yny;q.push(now);}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinwh;w2*w1;h2*h1;init();for(ll i0;icnt;i){bfs(ex[i],ey[i]);for(ll j0;j210;j)fill(used[j],used[j]210,0);}for(ll i1;ih;i)for(ll j1;jw;j)if(dis[i][j]INF)ansmax(ans,dis[i][j]);coutans/2endl;return0;}