hdu1242-搜索小练

很明显是个搜索题。开始就写。好久没写搜索的缘故，对自己的代码不自信呀，然后，写好就TLE啦。后来想想才知道，对于最少步数，最好用BFS，搜到就能结束。

改成BFS后，悲剧并没有结束，交了几次WA。测试了几组数据找不出错误，后来没忍住去看解题报告了，才发现应该用优先队列存储状态，步数小的优先搜索。改了一下就AC啦啦啦啦 加油！！吖飒~~~~

题意：

给出地图，求最少步数。其中a是目标，r是起点，x是时间多加1的点。

分析，

对于每个状态，搜索后再修改状态。优先队列需要重载<，使c小的在前。

代码：

把DFS一起附上，当模板看

#include<iostream>
#include<queue>
using namespace std;
char map[205][205];
int endx,endy;
int Min;int n,m;
struct info
{
	int x,y,c;
};
//深搜
bool DFS(int bx,int by,int cnt)
{
	char c;
	if(bx==endx&&by==endy) 
	{
		if(cnt<Min) Min=cnt;
		return true;
	}
	if(map[bx-1][by]!='#') //上
	{
		if(map[bx-1][by]=='x') cnt++;
		c=map[bx-1][by];
		map[bx-1][by]='#';
		DFS(bx-1,by,cnt+1);
		map[bx-1][by]=c;
	}
	if(map[bx+1][by]!='#') //下
	{
		if(map[bx+1][by]=='x') cnt++;
		c=map[bx+1][by];
		map[bx+1][by]='#';
		DFS(bx+1,by,cnt+1);
		map[bx+1][by]=c;
	}
	if(map[bx][by+1]!='#') //右
	{
		if(map[bx][by+1]=='x') cnt++;
		c=map[bx][by+1];
		map[bx][by+1]='#';
		DFS(bx,by+1,cnt+1);
		map[bx][by+1]=c;
	}
	if(map[bx][by-1]!='#') //左
	{
		if(map[bx][by-1]=='x') cnt++;
		c=map[bx][by-1];
		map[bx][by-1]='#';
		DFS(bx,by-1,cnt+1);
		map[bx][by-1]=c;
	}
	if(Min==n*m) return false;
}
//广搜
bool operator<(info a, info b) {return a.c > b.c;}
void BFS(info X)
{
	char cc;
	priority_queue<info> Q;
	Q.push(X);
	while(!Q.empty())
	{
		X=Q.top();
		Q.pop();
		map[X.x][X.y]='#';//已搜过
		if(X.x==endx&&X.y==endy) {Min=X.c;break;}		
		info A,B,C,D;
		if(map[X.x-1][X.y]!='#') //上
		{
			A.c=X.c+1;A.x=X.x-1;A.y=X.y;
			if(map[X.x-1][X.y]=='x') A.c++;
			Q.push(A);
		}
		if(map[X.x+1][X.y]!='#') //下
		{
			B.c=X.c+1;B.x=X.x+1;B.y=X.y;
			if(map[X.x+1][X.y]=='x') B.c++;
			Q.push(B);
		}
		if(map[X.x][X.y+1]!='#') //右
		{
			C.c=X.c+1;C.x=X.x;C.y=X.y+1;
			if(map[X.x][X.y+1]=='x') C.c++;
			Q.push(C);
		}
		if(map[X.x][X.y-1]!='#') //左
		{
			D.c=X.c+1;D.x=X.x;D.y=X.y-1;
			if(map[X.x][X.y-1]=='x') D.c++;
			Q.push(D);
		}
	}
	while(!Q.empty())
	{
		Q.pop();
	}
}
int main()
{                                                                                                                                                                                                                                                                                                 
	while(~scanf("%d%d",&n,&m))
	{
		getchar();
		Min=0;
		int i,j;
		for(i=0;i<=n+1;i++)
		{
			map[i][0]='#';//第一列
			map[i][m+1]='#';//最后一列
		}
		for(i=0;i<=m+1;i++)//行
		{
			map[0][i]='#';//第一行
			map[n+1][i]='#';//最后一行
		}
		int bx,by;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&map[i][j]);
				if(map[i][j]=='a') {endx=i;endy=j;}
				else if(map[i][j]=='r') {bx=i;by=j;map[i][j]='#';}
			}
			getchar();
		}
// 		if(!DFS(bx,by,0))
// 		printf("Poor ANGEL has to stay in the prison all his life.\n");
// 		else printf("%d\n",Min);
		info B;
		B.c=0;B.x=bx;B.y=by;
		//最少步数用广搜，一搜到就是最少步数。
		BFS(B);
		if(!Min) printf("Poor ANGEL has to stay in the prison all his life.\n");
 		else printf("%d\n",Min);
	}
	return 0;
}