当前位置: 首页> 科技> IT业 > 洛谷:B3625 迷宫寻路

洛谷:B3625 迷宫寻路

时间:2025/7/11 7:56:47来源:https://blog.csdn.net/qq_74924951/article/details/141169757 浏览次数:0次

迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n × m n\times m n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置,问能否走到 ( n , m ) (n, m) (n,m) 位置。

输入格式

第一行,两个正整数 n , m n,m n,m

接下来 n n n 行,输入这个迷宫。每行输入一个长为 m m m 的字符串,# 表示墙,. 表示空地。

输出格式

仅一行,一个字符串。如果机器猫能走到 ( n , m ) (n, m) (n,m),则输出 Yes;否则输出 No

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

提示

样例解释

路线如下: ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 3 , 2 ) → ( 3 , 3 ) → ( 2 , 3 ) → ( 2 , 4 ) → ( 2 , 5 ) → ( 3 , 5 ) (1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5) (1,1)(2,1)(3,1)(3,2)(3,3)(2,3)(2,4)(2,5)(3,5)

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1n,m100,且 ( 1 , 1 ) (1,1) (1,1) ( n , m ) (n, m) (n,m) 均为空地。

BFS板子题

#include<bits/stdc++.h>
//#include<iostream>
//#include<iomanip>
//#include<vector>
//#include<queue>
//#include<algorithm>
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
#define pii pair<int,int>
#define endl '\n'
const int M=2e5+7;
char a[200][200];
int vis[200][200];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m;
void bfs(int qx,int qy)
{queue<pii>q ;q.push({qx,qy});vis[1][1]=1;while(q.size()){auto [x,y]=q.front();q.pop();rep(i,0,3){int xx=x+dx[i],yy=y+dy[i];if(xx<1 ||xx > n || yy<1||yy>m)continue;if(vis[xx][yy] || a[xx][yy]=='#')continue;q.push({xx,yy});vis[xx][yy]=1;}}
}int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);cin>>n>>m;
rep(i,1,n)rep(j,1,m) cin>>a[i][j];bfs(1,1);
if(vis[n][m])cout<<"Yes";
else cout<<"No";return 0;
}
关键字:洛谷:B3625 迷宫寻路

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: