優先隊列 + BFS

題目描述

乍一看是BFS最短路徑，但仔細思考下，發現最短路徑不一定是時間最短的，是以需要求最短時間，用優先隊列去存儲狀态。

#include<bits/stdc++.h>
using namespace std;
int n,m,t,vis[105][105];
char arr[105][105];
int sx,sy,ex,ey,ans ;
struct node{
	int x,y,num;
	friend bool operator < (node x,node y){			
		return x.num > y.num;						//與sort函數的比較函數相反
	}
};
int var[4][2] = {1,0,-1,0,0,1,0,-1};
void bfs(){
	node n1;
	n1.x = sx;
	n1.y = sy;
	n1.num = 0;
	priority_queue<node>q;
	q.push(n1);
	
	while(!q.empty()){
		node nt = q.top();
		q.pop();
		if(nt.x == ex && nt.y == ey){
			ans = nt.num;
			return ;
		}
		for(int i = 0;i<4;i++){
			int dx = nt.x + var[i][0];
			int dy = nt.y + var[i][1];
			if(dx <= n&& dx >= 1 && dy>= 1&&dy<= m){
				if(vis[dx][dy] == 0 && arr[dx][dy] != '#'){
					vis[dx][dy] = 1;
					node n2;
					n2.x = dx;
					n2.y = dy;
					if(arr[dx][dy] == 'x'){
						n2.num = nt.num + 2; 
					}
					else{
						n2.num = nt.num + 1; 
					}
					q.push(n2);
				}
			}
		}
	}
}
int main(){
	//freopen("a.txt","r",stdin);
	cin>>t;
	while(t--){
		ans = -1;
		memset(vis,0,sizeof vis);
		memset(arr,0,sizeof arr);
		cin>>n>>m;
		for(int i = 1;i<= n;i++){
			for(int j = 1;j<= m;j++){
				cin>>arr[i][j];
				if(arr[i][j] == 'r'){
					sx = i;
					sy = j;
				}
				if(arr[i][j] == 'a'){
					ex = i;
					ey = j;
				}
			}
		}
		bfs();
		if(ans == -1 ){
			cout<<"Impossible"<<endl; 
		}
		else{
			cout<<ans<<endl;
		}
	}
	return 0;
}