一开始还没学BFS,前几次都是用DFS,但很明显,这样做会TLE,于是后来学了BFS之后,改用BFS,就AC了。
代码如下:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=205;
char s[maxn][maxn];
int h,l,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool vis[maxn][maxn];
struct block
{
char c;
int x,y;
int mov;
block(char c, int x, int y, int mov){ this->c=c; this->x=x; this->y=y; this->mov=mov; };
};
bool BFS(int xs,int ys)
{
queue<block> Q;
memset(vis,0,sizeof(vis));
Q.push( block('r',xs,ys,0) );
vis[xs][ys]=1;
while(!Q.empty())
{
block fro=Q.front(); Q.pop();
int x=fro.x,y=fro.y,mov=fro.mov; char c=fro.c;
if(c=='a')
{
printf("%d\n",mov);
return true;
}
if(c=='x')
{
Q.push( block('.',x,y,mov+1) ); //遇到敌人,原地不动,move+1
continue;
}
for(int i=0;i<=3;i++)
{
int x0=x+dir[i][0],y0=y+dir[i][1];
if(x0<h&&x0>=0&&y0<l&&y0>=0) //不能越界
{
if(s[x0][y0]!='#'&&!vis[x0][y0]) //不是墙,未被访问
{
Q.push( block(s[x0][y0],x0,y0,mov+1) );
vis[x0][y0]=1;
}
}
}
}
return false;
}
int main()
{
int x,y,flag;
while(~scanf("%d%d",&h,&l))
{
flag=0;
for(int i=0;i<=h-1;i++)
{
scanf("%s",s[i]);
if(flag) continue;
for(int j=0;j<=l-1;j++)
if(s[i][j]=='r')
{
flag=1;
x=i;
y=j;
break;
}
}
if(!BFS(x,y))
printf("Poor ANGEL has to stay in the * all his life.\n");
}
return 0;
}