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;
}