1242 rescue.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//bfs ，第一解为最优解 
//dfs超时 
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
char map[201][201],ct;
int len[201][201];//难处在于杀人后的时间顺序 
int n,m;
struct infor
{
	int x,y,time;
	bool operator == (const infor &t) const
	{
		return x==t.x && y==t.y;
	}
	char state ()
	{
		if(x<0 || y<0 || x>=n || y>=m)
			return '#';
		return map[x][y];
	}
	void maketag()
	{
		map[x][y]='#';
	}
	void kill()
	{
		time++;
		map[x][y]='k';
		len[x][y]=time;
	}
};
infor rp,ap;
queue<infor> SQ;

void bfs()
{
	infor t,t2;
	char ct;
	
	while(!SQ.empty())
	{
		t=SQ.front();
		SQ.pop();
		ct=t.state();
		if(ct!='#')
		{
			if(t==ap && t.time<ap.time)
			{
				ap.time=t.time;
				return;
			}
			if(ct=='x')
			{
				t.kill();
				SQ.push(t);
			}
			else if( ct=='.' || (ct=='k' && len[t.x][t.y]==t.time) )//len用于确认是谁杀的 
			{
				t.maketag();
				
				t2=t;t2.x--;t2.time++;
				ct=t2.state();
				if(ct!='#')
					SQ.push(t2);
					
				t2=t;t2.x++;t2.time++; 
				ct=t2.state();
				if(ct!='#')
					SQ.push(t2);
					
				t2=t;t2.y--;t2.time++;
				ct=t2.state();
				if(ct!='#')
					SQ.push(t2);
					
				t2=t;t2.y++;t2.time++;
				ct=t2.state();
				if(ct!='#')
					SQ.push(t2);
			}
		}//if
	}
}

int main()
{
	int i,j;
	
	while( scanf("%d %d",&n,&m)!=EOF )
	{
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				if(map[i][j]=='r')
				{
					rp.x=i;
					rp.y=j;
					rp.time=0;
					map[i][j]='.';
				}
				else if(map[i][j]=='a')
				{
					ap.x=i;
					ap.y=j;
					map[i][j]='.';
					ap.time=0x7fffffff;
				}
		memset(len,0,sizeof(len));
		while(!SQ.empty())
			SQ.pop();
		SQ.push( rp );
		bfs();
		if(ap.time!=0x7fffffff)
			printf("%d\n",ap.time);
		else
			printf("Poor ANGEL has to stay in the prison all his life.\n");
	}
	return 0;
}