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

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

相关推荐

iPhone17护眼钢化膜哪个好？悟赫德观复盾实测对比

iPhone17护眼钢化膜怎么选？悟赫德三大黄金标准避坑指南

游戏离线订阅功能实现

更多资讯

数据中心机房建设方案：从容量定义到供配电制冷与运维验证

DDR5内存SPD读取实战：用i2c-tools解析SPD5118 Hub数据

基于DeepSeek与RAG构建酒店投诉处理知识库的落地实践

Redis INCR命令深度解析：高并发计数器的原子性原理与工程实践

CV800大巴空调驱动器：CAN通讯、参数烧录与EMI排错

ROS2+Docker+VS Code机器人Python开发实战

今日更新

AWS无服务器应用开发指南：从Lambda到SAM的架构与实践

SpringBoot+Vue人事系统实战：解决HR数据断点与事务一致性

MATLAB手写紧束缚模型计算石墨烯能带结构

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？