POJ 2312 Battle City 优先多列+bfs

来源：http://poj.org/problem?id=2312

题意：题目背景就是小时候玩的坦克大战，求从起点到终点最少需要多少步。已知S和R是不能走得，E是空的，可以走，B是砖，只有打掉后才可以通过。

思路：很容易看出来这是一道广搜的题目，但是因为走E和走B所需要的时间不一样，因此不能用普通的队列存点。因为对于走B来说，要先打掉砖才能通过，所以我们可以理解为走B需要两步，而走E是指需要1步的。因此，不能用普通队列来存。我们可以用STL中的优先队列来存，每次从队头取出的都是步数少的点就可以了。这样最先搜到的就是最优解。

代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
struct point{
	int x,y,step;
	bool operator < (const point & p) const{
	   return step > p.step;
	} 
};
const int N = 305;
char map[N][N];
int sx,sy,ex,ey,flag[N][N],row,col;
int addx[4] = {0,0,1,-1};
int addy[4] = {1,-1,0,0};
int bfs(){
	priority_queue<point> qq;
	point p;
	p.x = sx; p.y = sy; p.step = 0;
	flag[sx][sy] = 1;
	qq.push(p);
	while(!qq.empty()){
		point topp = qq.top();
		qq.pop();
		if(topp.x == ex && topp.y == ey){
			return topp.step;
		}
		else{
			for(int i = 0; i < 4; ++i){
			   int newx = topp.x + addx[i];
			   int newy = topp.y + addy[i];
			   if(newx >= 0 && newx < row && newy >= 0 && newy < col && !flag[newx][newy] ){
				   if(map[newx][newy] == 'S' || map[newx][newy] == 'R')
					   continue;
			      point newp;
				  newp.x = newx;
				  newp.y = newy;
				  flag[newx][newy] = 1;
				  if(map[newx][newy] == 'B'){
					  newp.step = topp.step + 2;
				  }
				  else
					  newp.step = topp.step + 1;
				  qq.push(newp);
			   }
			}
		}
	}
	return -1;
}
int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%d%d",&row,&col) != EOF){
	   if(row + col == 0)
		   break;
	   CLR(flag,0);
	   CLR(map,'0');
	   for(int i = 0; i < row; ++i){
	      for(int j = 0; j < col; ++j){
			  cin >> map[i][j];
			  if(map[i][j] == 'Y'){
			    sx = i;
				sy = j;
			  }
			  else if(map[i][j] == 'T'){
			    ex = i;
				ey = j;
			  }
		  }
	   }
	  int ans = bfs();
	  printf("%d\n",ans);
	}
	return 0;
}