HDU1242,Rescue(BFS)

一开始还没学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;
}
上一篇:PAT甲级-11076 Forwards on Weibo (30 分)


下一篇:【论文阅读】Towards emotion recognition in immersive virtual environments: A method for Facial emotion rec