电商网站如何做精细化运营,天蝎网络服务公司,建设网站 软件,做网站阿里云记录值怎么填迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n m n\times m nm 矩阵#xff0c;每个位置要么是空地#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置#xff0c;问能否…迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 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 1≤n,m≤100且 ( 1 , 1 ) (1,1) (1,1) 和 ( n , m ) (n, m) (n,m) 均为空地。
BFS板子题
#includebits/stdc.h
//#includeiostream
//#includeiomanip
//#includevector
//#includequeue
//#includealgorithm
#define rep(i,l,r) for(int il;ir;i)
using namespace std;
#define pii pairint,int
#define endl \n
const int M2e57;
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)
{queuepiiq ;q.push({qx,qy});vis[1][1]1;while(q.size()){auto [x,y]q.front();q.pop();rep(i,0,3){int xxxdx[i],yyydy[i];if(xx1 ||xx n || yy1||yym)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);cinnm;
rep(i,1,n)rep(j,1,m) cina[i][j];bfs(1,1);
if(vis[n][m])coutYes;
else coutNo;return 0;
}
