时间限制: 1 Sec 内存限制: 64 MB
提交: 42 解决: 9
[提交][状态][讨论版]
题目描述
Angel被人抓住关在一个迷宫了！迷宫的长、宽均不超过200，迷宫中有不可以越过的墙以及*的看守。Angel的朋友带了一个救援队来到了迷宫中。他们的任务是：接近Angel。我们假设接近Angel就是到达Angel所在的位置。
假设移动需要1单位时间，杀死一个看守也需要1单位时间。到达一个格子以后，如果该格子有看守，则一定要杀死。交给你的任务是，最少要多少单位时间，才能到达Angel所在的地方（只能向上、下、左、右4个方向移动）?
输入
第1行两个整数n，m。表示迷宫的大小为n×m。
以后n行，每行m个字符。其中“#”代表墙，“．”表示可以移动，“x”表示看守，“a”表示Angel，“r”表示救援队伍。字母均为小写。
输出
l行，代表救出Angel的最短时间。如果救援小组永远不能达到Angel处，则输出“NO ANSWER”。
样例输入
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
样例输出
13 【分析】 前期做一些小小的处理，后面就是简单的BFS一下。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define pi acos(-1.0)
#define inf 0x3f3f3f3f
using namespace std;
int n,m,flag=;
int dis[][]= {,,,,-,,,-};
int vis[][];
string w[];
struct man
{
int x,y,step;
};
queue<man>q;
void bfs(man s)
{
q.push(s);
while(!q.empty())
{
man t=q.front();
//printf("%d %d %d\n",t.x,t.y,t.step);
if(w[t.x][t.y]=='a'){printf("%d\n",t.step);flag=;return;}
else if(w[t.x][t.y]=='x'){t.step++;q.pop();q.push(t);w[t.x][t.y]='.';continue;}
q.pop();
for(int i=;i<;i++)
{
int xx=t.x+dis[i][];int yy=t.y+dis[i][];
if(xx>=&&xx<n&&yy>=&&yy<m&&vis[xx][yy]==&&w[xx][yy]!='#')
{
man k;
vis[xx][yy]=;
k.step=t.step+;k.x=xx;k.y=yy;q.push(k);
}
}
}
}
int main()
{
memset(vis,,sizeof(vis));
scanf("%d%d",&n,&m);man s;
for(int i=;i<n;i++)cin>>w[i];
for(int i=; i<n; i++)
for(int j=; j<m; j++)
{
if(w[i][j]=='r')
{ s.x=i;
s.y=j;
s.step=;
}
}
bfs(s);
if(flag==)printf("NO ANSWER\n");
return ;
}
ViewCode