demo1

迷宫的游戏，相信大家都听过，现在我们用一个n*m的矩阵表示一个迷宫，例如：

S.X.
..X.
..XD
....

其中‘S’表示起点，‘D’表示终点，‘X’表示该位置为墙，不可以走，‘.’表示可以通行。每次只能向“上下左右”四个方向移动一步。

      你的任务是判断在x步内（小于等于x），能否从起点走到终点。


输入格式
第一行输入三个数n m x，分别表示迷宫的尺寸和步数。（1 < n，m < 7； 0 < x < 50）

接下来输入一个n*m的矩阵，描述迷宫的状态。
输出格式
判断是否能在x步内从起点走到终点，如果可以，输出“YES”，否则输出“NO”。

样例
输入数据 1
3 4 5
S.X.
..X.
...D
输出数据 1
YES

DKX

2023-08-02 17:40:46

#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+5;
int n,m,k,stx,sty,edx,edy,dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char a[MAXN][MAXN];
bool flag[MAXN][MAXN];
struct PR{
	int x,y,t;
};
void bfs(){
	PR op;
	queue<PR> q;
	q.push({stx,sty,0});
	while(!q.empty()){
		op=q.front(),q.pop();
		if(op.x==edx&&op.y==edy&&op.t<=k){
			puts("YES");
			exit(0);
		}
		for(int i=0;i<4;i++){
			int nx=op.x+dir[i][0],ny=op.y+dir[i][1],nt=op.t+1;
			if(!flag[nx][ny]&&nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='X'){
				flag[nx][ny]=1;
				q.push({nx,ny,nt});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='S')	stx=i,sty=j;
			if(a[i][j]=='D')	edx=i,edy=j;
		}
	}
	bfs();
	puts("NO");
	return 0;
}

共 1 条回复