NYOJ - 284 - 坦克大战(BFS求最短路,优先队列)

题目传送门~~~~

题目的意思就是输如n和m再给定一个n*m的地图，如：

3 4
YBEB
EERE
SSTE
           

其中Y表示You的位置，即起点。T表示Target的位置，即终点。S和R不能通过，通过E需要1步，通过B需要2步，求Y到T的所需要的最少部署。求最少步数首先想到bfs，但是如果用普通队列的话，如图：

SEBY
STBB
           

从Y开始搜索，先向下再向左，首先<(1,3)2步> 入队，然后<(0,2)2步>入队，对手<(1,3)2步>搜索到<(1,2)4步>入队后，自己出队，然后<(0,2)2步>搜索<(0,1)3步>入队后，自己出队，到目前位置，搜索到了<(0,1)3步>和<(1,2)4步> 在这两个点都是只需要走一步就可以达到搜索边界，就会退出搜索输出答案，但是此时<(1,2)4步>在队首，所以输出的答案就是5(错误的)，那么如何把当前队列中步数少的结点<(0,1)3步>移动到队首呢，这里用到了优先队列。说到这里也许有人会问 ，那为什么以前用普通队列就能搜到最短路，那是因为每次移动的时候，都是消耗相同的步数。假设走过B和E的步数都是1，从Y-B-E-T 和Y-B-B-T这两条路不论哪一条先搜到终点。步数都是3。

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

int x1,y1,x2,y2,ans,n,m;
int vis[305][305];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
char map[305][305];


struct Point{
	int x,y,steps;
	friend bool operator<(Point a,Point b){
		return a.steps>b.steps;
	}
};


void bfs(){
	if(x1==x2&&y1==y2){
		ans = 0;
		return ;
	}
	priority_queue<Point>q;
	Point v1;
	v1.x = x1;
	v1.y = y1;
	v1.steps = 0;
	vis[x1][y1] = 1;
	q.push(v1);	
	
	while(!q.empty()){
		Point v2;
		for(int i=0 ;i<4 ;i++){
			v2.x = q.top().x + dir[i][0];
			v2.y = q.top().y + dir[i][1];
			if(v2.x==x2&&v2.y==y2){
				ans = q.top().steps+1;
				break;
			}
			
			if(v2.x>=0&&v2.y>=0&&v2.x<n&&v2.y<m&&!vis[v2.x][v2.y]&&(map[v2.x][v2.y]!='S'&&map[v2.x][v2.y]!='R')){
				if(map[v2.x][v2.y]=='B'){
					v2.steps = q.top().steps+2;
				}else{
					v2.steps = q.top().steps+1;
				}
				vis[v2.x][v2.y] = 1;
				q.push(v2);
			}
		}
		if(v2.x==x2&&v2.y==y2){
			ans = q.top().steps+1;
			break;
		}
		q.pop();
	}
	
	
	
}

int main(){
	while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
		memset(vis,0,sizeof(map));
		ans = -1;
		getchar();
		for(int i=0 ;i<n ;i++){
			gets(map[i]);
			for(int j=0 ;j<m ;j++){
				if(map[i][j]=='Y'){
					x1 = i;
					y1 = j;
				}
				if(map[i][j]=='T'){
					x2 = i;
					y2 = j;
				}
			}
		}
		bfs();
		printf("%d\n",ans);
	}
	return 0;
}