Rescue

62 阅读 0 评论 41 点赞

我是靠谱客的博主忧郁鼠标，最近开发中收集的这篇文章主要介绍Rescue，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

InputFirst line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.
OutputFor each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."
Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

被困的天使——a,#——围墙，r——天使的朋友，.——可以走的路,x——守卫。算出r救出a的最短时间。如果遇到守卫天数+1.

BFS的思路就是找出天使离最近的朋友的最短距离。（因为天使的朋友不一定是一个，所以要从天使的位置开始找最近的朋友的距离），设置一个全局变量ans，赋值最大值200*200=40000，当步数>=最大值的时候就跳出循环，其实也相当于一个剪枝了。

BFS代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,m,ans,ax,ay;
bool flag;
char prison[201][201];
int vis[201][201];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y,int step)
{
int i,x1,y1;
if(step>=ans)
return;
if(prison[x][y]=='r')
{
flag=1;
if(step<ans)
ans=step;
return;
}
for(i=0;i<4;i++)
{
x1=x+dir[i][0];
y1=y+dir[i][1];
if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&prison[x1][y1]!='#'&&vis[x1][y1]==0)
{
if(prison[x][y]=='x')
step++;
vis[x1][y1]=1;
dfs(x1,y1,step+1);
vis[x1][y1]=0;
if(prison[x][y]=='x')
step--;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
getchar();
memset(vis,0,sizeof(vis));
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>prison[i][j];
if(prison[i][j]=='a')
{
ax=i;
ay=j;
}
}
}
flag=0;
ans=40000;
vis[ax][ay]=1;
dfs(ax,ay,0);
if(flag)
printf("%dn",ans);
else
printf("Poor ANGEL has to stay in the prison all his life.n");
}
return 0;
}