NYOJ - 1100 - WAJUEJI which home strong！(BFS變形,優先隊列)

輸入

第一個數T，T組測試資料。

兩個數 n, m; ( 0< n , m <= 100 ) 表示一個h行m列的二維地圖。

接下來n行每行m 個字元。

‘s’ 表示弟弟目前所在位置。

‘# ’表示此處為一座山。為了節省體力，不從此處通行。

從‘A’-‘Z’表示各地的經濟水準，對應1-26，路過對應字元的地區需要交對應的生活費。

‘l’表示藍翔技校的所在地。

s 與 l 均為小寫字母。

弟弟隻能走四個方向。

輸出

輸出一個數表示弟弟到達藍翔需要的生活費最小是多少。

如果不能到達，輸出 -1。

樣例輸入

3
3 5
#sVGF
A##ZA
lCDBC
3 3
sAB
ABS
ABl
3 3
s#B
###
ABl
           

樣例輸出

48
4
-1
           

題目大概意思是，給定一個n*m的圖，s點的位置表示起點，l(小寫字母L)點的位置表示重點的位置，其中#表示無法走的，ABCD....Z分别表示城市，并且分别對應(1~26)表示經過城市所需要的花費。現在要求從起點到重點所需要花費的最少費用是多少，如果無法到達輸出-1。

思路：提到最短路徑，首先想到的是bfs，但是這道題是要求最少的花費，花費最少時，不一定就是最短路。比如說

#####
#sZl#
#AAA#
#####
           

從s到l的最少步數是2 但是花費是26，而最少花費是3，但是步數是4。那麼想要利用bfs找到最少的花費應該怎麼做。

這裡我用了優先隊列，重載運算符後。在出隊的時候，花費最少的先出隊，即，優先從花費最少的地方搜尋。從s先搜尋，<(0,0)花費0>  入隊，搜尋後<(0,1)花費26> 和<(1,0)花費1 >入隊，因為花費少的優先出隊，是以從(1,0)開始搜尋，<(1,2)花費2>入隊，同理<(1,3)花費3>入隊，在(1,3)搜尋時，搜到重點l，退出搜尋，輸出結果。

struct Point{
	int x,y,money;
	//重載小于運算符  
	friend  bool operator<(Point a,Point b){
		//money小的優先出隊 
		return a.money>b.money; 
	}
};
           

完整AC代碼：

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct Point{
	int x,y,money;
	//重載小于運算符  
	friend  bool operator<(Point a,Point b){
		//money小的優先出隊 
		return a.money>b.money; 
	}
};


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

void bfs(){
	if(x1==x2&&y1==y2){
		ans = 0;
		return ;
	}
	priority_queue<Point>q;//優先隊列 money越小越好 
	Point v1;
	v1.x = x1;
	v1.y = y1;
	v1.money = 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>=0&&v2.x<n&&v2.y>=0&&v2.y<m&&!vis[v2.x][v2.y]&&map[v2.x][v2.y]!='#'){
				if(v2.x==x2&&v2.y==y2){
					ans = q.top().money;
					break;
				}
				v2.money = q.top().money + (int)(map[v2.x][v2.y]-'A'+1);
				vis[v2.x][v2.y] = 1;
				q.push(v2);
				
			}
		}
		if(v2.x==x2&&v2.y==y2){
			return ;
		}
		q.pop();
	}
	
}

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