Monsters
Wrong Answer
72
提交记录
| C++11 | Wrong Answer | 72 分 | 2024-05-30 16:49:45UTC+8 | |
|---|---|---|---|---|
| C++14 | Wrong Answer | 72 分 | 2024-04-26 17:45:39UTC+8 | |
| C++14 | Compile Error | 0 分 | 2024-04-26 17:45:27UTC+8 | |
| C++14 | Wrong Answer | 72 分 | 2024-04-26 17:44:53UTC+8 |
时间限制：1s 空间限制：256MB
题目描述
你和一些怪物在迷宫里。当你在迷宫中向某个方向迈出一步时，每个怪物也可能同时迈出一步。
你的目标是到达一个没有怪物存在的位于迷宫边界（迷宫最上面或者最下面那行，最左或者最右那列）的格子。
你的任务是判断这是否可行，如果可行，打印一条你可以遵循的路径。
注意：你的计划必须在任何情况下都有效，即使怪物事先知道你的路径。
输入格式
第一行输入 �,�n,m ,代表迷宫的行与列。(1≤�,�≤1000)(1≤n,m≤1000)
接下来 �n 行 �m 列个字符，代表迷宫。
. (代表道路), # (代表是障碍), A (代表起点), M (代表怪物)。
保证迷宫中一定会有一个 A
输出格式
如果可以找到，
第一行输出 YES ，在第二行输出路径长度，第三行输出由D, U, L, R（代表下，上，左，右）组成的路径，
如果找不到，输出 NO。
你可以输出任意一条长度不超过 �⋅�n⋅m 的路径。
样例输入
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
样例输出
YES
5
RRDDR
有思路，但不知道路径怎么打印：
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int x,y,step;
};
queue<node> q;
queue<node> qq;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char a[1001][1001];
int n,m,vis[1001][1001],cnt[1001][1001],cnt1[1001][1001],ax,ay;
void bfs(){
while(!q.empty()){
for(int i=0;i<4;i++){
int tx=q.front().x+dx[i];
int ty=q.front().y+dy[i];
if(tx>=1&&ty<=m&&tx>=1&&ty<=n&&vis[tx][ty]==0&&a[tx][ty]!='#'){
cnt[tx][ty]=cnt[q.front().x][q.front().y]+1;
q.push(node{tx,ty,q.front().step+1});
vis[tx][ty]=1;
}
}
q.pop();
}
}
void bfs1(){
while(!qq.empty()){
for(int i=0;i<4;i++){
int tx=qq.front().x+dx[i];
int ty=qq.front().y+dy[i];
if(tx>=1&&ty<=m&&tx>=1&&ty<=n&&vis[tx][ty]==0&&a[tx][ty]!='#'){
if(tx==n||tx==1||ty==1||ty==m){
return ;
}
cnt1[tx][ty]=cnt1[qq.front().x][qq.front().y]+1;
qq.push(node{tx,ty,qq.front().step+1});
vis[tx][ty]=1;
}
}
qq.pop();
}
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='M'){
q.push(node{i,j,1});
cnt[i][j]=0;
}else if(a[i][j]=='A'){
qq.push(node{i,j,1});
cnt1[i][j]=0;
}
}
}
bfs();
bfs1();
/*
后面的打印路径就不会了
*/
return 0;
}