5. Monsters
XJOI - 题目ID：14068必做题100分
最新提交：
Wrong Answer
72 分
历史最高：
Wrong Answer
72 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
时间限制：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>
using namespace std;
char a[1005][1005];
int n,m;
int mstep[1005][1005];
int astep[1005][1005];
string al[1005][1005];
bool vis[1005][1005];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
string d[]={"D","R","U","L"};
int cnt;
struct node{
int x,y;
};
void bfs(int sx,int sy){
memset(vis,0,sizeof(vis));
queue<node>q;
q.push(node{sx,sy});
vis[sx][sy]=1;
mstep[sx][sy]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=mstep[x][y];
q.pop();
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&vis[tx][ty]==0&&a[tx][ty]!='#'){
vis[tx][ty]=1;
q.push(node{tx,ty});
mstep[tx][ty]=min(mstep[tx][ty],s+1);
}
}
}
}
void abfs(int sx,int sy){
memset(vis,0,sizeof(vis));
queue<node>q;
q.push(node{sx,sy});
vis[sx][sy]=1;
astep[sx][sy]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=astep[x][y];
q.pop();
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&vis[tx][ty]==0&&a[tx][ty]!='#'){
vis[tx][ty]=1;
q.push(node{tx,ty});
astep[tx][ty]=s+1;
al[tx][ty]=al[x][y]+d[i];
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
mstep[i][j]=1e9;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='M'){
cnt++;
bfs(i,j);
}
else if(a[i][j]=='A'){
abfs(i,j);
}
}
}
bool f=0;
int x,y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1||i==n||j==1||j==m){
if(astep[i][j]<mstep[i][j]&&a[i][j]!='#'&&al[i][j].length()<=n*m){
f=1;
x=i;
y=j;
}
}
}
}
string ans="";
if(f) cout<<"YES"<<endl;
else{
cout<<"NO";
return 0;
}
cout<<astep[x][y]<<endl;
cout<<al[x][y];
return 0;
}