6. 营救计划
XJOI - 题目ID：3585必做题100分
最新提交：
Wrong Answer
40 分
历史最高：
Wrong Answer
40 分
时间限制: 200ms
空间限制: 131072kB
题目描述
时间限制：0.2s 空间限制：128M
题目描述：
在一个 𝑛∗𝑚n∗m 的迷宫里，有一个萌新被困住了，你作为一个久经码场的战士，决定去营救萌新。地图中还会有一些守卫，你必须打败守卫才能通过守卫所在的位置，打败守卫需要花费 1 分钟，移动一步也需要花费 1 分钟，每次你只能往上下左右某个方向移动一步。问你最少需要花费多少时间才能救到萌新。
输入格式：
第一行输入两个整数 𝑛,𝑚n,m。(1≤ 𝑛,𝑚≤ 1000)(1≤ n,m≤ 1000)
接下来 𝑛n 行每行输入 𝑚m 个字符
‘#’ 代表障碍物，无法直接通过
‘.’ 代表空地，可以直接通过
‘G’ 代表守卫，你需要打败他才能通过
‘M’ 代表萌新所在的位置
‘@’ 表示你所在的位置
输出格式：
如果可以营救到萌新，就输出最少需要花费的分钟数
如果不可以，则输出 “You can’t save Mengxin”
样例输入1：
7 8
#.#####.
#.M#…@.
#…#G…
…#…#.#
#…##…
.#…
…
样例输出1：
13
样例输入2：
2 2
M.
G@
样例输出2：
2
我的代码：
#include<iostream>
#include<queue>
using namespace std;
int n,m;
char a[1005][1005];
bool vis[1005][1005];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
int sx,sy,ex,ey;
struct node{
int x,y,step;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx=i;
sy=j;
}
else if(a[i][j]=='M'){
ex=i;
ey=j;
}
}
}
queue<node>q;
q.push(node{sx,sy,0});
vis[sx][sy]=1;
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=q.front().step;
q.pop();
if(x==ex&&y==ey){
cout<<s;
return 0;
}
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]!='#'){
if(a[tx][ty]!='G') q.push(node{tx,ty,s+1});
else q.push(node{tx,ty,s+2});
vis[tx][ty]=1;
}
}
}
cout<<"You can't save Mengxin";
return 0;
}
