P1519 穿越栅栏 Overfencing 【洛谷算法习题】-平芜编程栈

P1519 穿越栅栏 Overfencing

网页链接

P1519 穿越栅栏 Overfencing

题目描述

Farmer John 在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。

给定迷宫的宽度W WW（1 ≤ W ≤ 38 1 \leq W \leq 381≤W≤38）及高度H HH（1 ≤ H ≤ 100 1 \leq H \leq 1001≤H≤100）。2 × H + 1 2 \times H+12×H+1行，每行2 × W + 1 2 \times W+12×W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）。

当然了，牛们只会水平或垂直地在 X 或 Y 轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）。

这是一个W = 5 , H = 3 W=5,H=3W=5,H=3的迷宫：

+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。

输入格式

第一行两个整数W , H W,HW,H。

接下来2 × H + 1 2 \times H+12×H+1行：每行2 × W + 1 2 \times W+12×W+1个字符，描述一个迷宫。

输出格式

输出一个单独的整数，表示最坏情况下牛走出迷宫的最小步数。

输入输出样例 #1

输入 #1

5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+

输出 #1

说明/提示

翻译来自NOCOW

USACO 2.4

解题思路

本题是一个在字符迷宫中寻找最坏情况出口距离的搜索问题。核心在于将字符网格转化为可走的图，然后以两个出口为起点进行多源 BFS，求出每个格子到最近出口的最短距离，最后取最大值并换算为实际步数。

1. 问题等价转化

迷宫表示：给定W × H W \times HW×H的迷宫，实际字符图为( 2 H + 1 ) (2H+1)(2H+1)行、( 2 W + 1 ) (2W+1)(2W+1)列。奇数行、奇数列是墙壁（+、-、|），偶数行、偶数列是房间或通道。
可走节点：字符图中的空格' '表示牛可以站立的格子。代码中把这些空格标记为vis[i][j]=0，表示可以通行。
出口判定：牛从迷宫边界上的空格走出迷宫。代码将位于网格边界（第1行、最后一行、第1列、最后一列）且是空格的格子视为出口，记录其坐标，并设初始距离为 1（代表“移出迷宫的那一步”已计入）。
距离定义：在字符网格中，相邻可走空格之间的距离为 1。牛在迷宫中从一个房间移动到相邻房间，在字符图上需要走两步（例如从一个空格到隔壁空格，中间隔着墙壁）。因此，在字符网格上计算出的最短路长度恰好是实际步数的 2 倍，最终答案需除以 2。

2. 算法实现：多源 BFS

建图与标记：
- 读入W , H W, HW,H后，将其更新为字符图的真实宽高w = 2*W+1, h = 2*H+1。
- 用getline按行读取迷宫，对每行的每个字符判断：若是空格，则将vis[i][j]置为 0（可走）。
- 如果该空格位于边界，则将其记录为出口，坐标存入ex[], ey[]，同时初始化该点的dis = 1。
多源 BFS：
- 依次以每个出口为起点执行 BFS。使用队列queue<nd>，used数组控制访问去重（每次 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×77=15477，每条边最多四个方向，两次 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。

代码内容

#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;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;queue<nd>q;voidinit(){cin.getline(s,500);for(ll i=0;i<210;i++){fill(dis[i],dis[i]+210,INF);fill(vis[i],vis[i]+210,1);}for(ll i=1;i<=h;i++){cin.getline(s,500);for(ll j=1;j<=w;j++)if(s[j-1]==' '){vis[i][j]=0;if((i==1||j==1||i==h||j==w)&&vis[i][j]==0){ex[cnt]=i;ey[cnt]=j;dis[i][j]=1;cnt++;}}}}voidbfs(ll x,ll y){nd st;st.x=x;st.y=y;q.push(st);used[x][y]=1;while(!q.empty()){nd cur=q.front();q.pop();for(ll i=0;i<4;i++){ll nx=cur.x+dx[i],ny=cur.y+dy[i];if(nx>0&&nx<=h&&ny>0&&ny<=w&&vis[nx][ny]==0&&used[nx][ny]==0){used[nx][ny]=1;dis[nx][ny]=min(dis[nx][ny],dis[cur.x][cur.y]+1);now.x=nx;now.y=ny;q.push(now);}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>w>>h;w=2*w+1;h=2*h+1;init();for(ll i=0;i<cnt;i++){bfs(ex[i],ey[i]);for(ll j=0;j<210;j++)fill(used[j],used[j]+210,0);}for(ll i=1;i<=h;i++)for(ll j=1;j<=w;j++)if(dis[i][j]<INF)ans=max(ans,dis[i][j]);cout<<ans/2<<endl;return0;}