计蒜客迷宫（bfs）

秒速五厘米 2024-02-17 22:15 6阅读 0赞

已知一个 n 行 m 列的上下左右四联通的迷宫，其中字符 'Y' 表示起点，字符 'C' 表示终点，在途中只有一个起点和终点，字符 '\*' 表示可通过的收费站，每通过一次需要花费 x 元，字符 '\#' 表示不可通过的点，字符 'P' 表示地道的出入口，在迷宫中所有的地道出入口都是联通的，并且通过地道不需要任何费用。求从起点到终点的最小花费。

**输入格式**

输入包含多组测试数据 ( 不超过50 组 ) ，对于每组测试数据：

第一行包含三个整数 n m x ( 0 ≤ n × m ≤ 5000 ; 0 < x ≤ 10000 ) 。

接下来 n 行每行包含 m 个字符，表示迷宫。其中字符 'P' 的数量不超过总字符数量的 10% 。

**输出格式**

对于每组测试数据，输出最小的花费，如果从起点不能到达终点，输出 -1 。

##### 样例输入 #####

1 3 2
    Y#C
    1 3 2
    Y*C
    2 5 2
    Y***C
    P###P

##### 样例输出 #####

-1
    2
    0

分析：bfs求解，遇到地下通道考虑其所有出口，用优先队列存储结点，权值小者先出队列。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn=5000+5;
    char g[maxn][maxn];
    int vis[maxn][maxn];
    struct node{
    	int x,y;
    	int w;
    	node(int x = 0,int y = 0,int w = 0):x(x),y(y),w(w){}
    	bool operator < (const node& nd)const {
    	return w>nd.w;
    	}
    }ns,nd;
    int n,m,x;
    vector<node>vec;
    int dir[][2]={
       {0,-1},{0,1},{-1,0},{1,0}};
    
    void bfs(){
    	memset(vis,0,sizeof(vis));
    	priority_queue<node>q;
    	q.push(ns);
    	vis[ns.x][ns.y]=1;
    	while(!q.empty()){
    		node u = q.top();
    		q.pop();
    		if(u.x == nd.x && u.y == nd.y){
    			printf("%d\n",u.w);
    			return ;
    		}
    		
    		for(int i=0;i<4;i++){
    			node v = node(u.x + dir[i][0],u.y + dir[i][1],u.w);
    			if(v.x >= n || v.y >= m || v.x < 0 || v.y <0)continue;
    			if(vis[v.x][v.y] || g[v.x][v.y] == '#')continue;
    			vis[v.x][v.y]=1;
    			if(g[v.x][v.y]=='P'){  //如果是地下通道 
    				for(int i=0;i<vec.size();i++){
    					int vx=vec[i].x,vy=vec[i].y;
    					if(vx == v.x && vy == v.y)continue;  
    					if(vis[vx][vy])continue;
    					q.push(node(vx,vy,v.w));
    					vis[vx][vy]=1;
    				}
    			}else if(g[v.x][v.y]=='*'){
    				v.w+=x;
    				q.push(v);
    			}
    			else {
    				q.push(v);
    			}
    		}
    	}
    	printf("-1\n");
    }
    
    int main(){
    	while(scanf("%d%d%d",&n,&m,&x)==3){
    		for(int i=0;i<n;i++)
    		scanf("%s",g[i]);
    		
    		for(int i = 0;i < n;i++){
    			for(int j = 0;j < m;j++){
    				if(g[i][j] == 'Y'){
    					ns.x = i,ns.y = j;
    				}
    				else if(g[i][j] == 'C'){
    					nd.x = i,nd.y = j;
    				}
    				else if(g[i][j] == 'P'){
    					vec.push_back(node(i,j));
    				}
    			}
    		}
    		
    		bfs();
    		vec.clear();
    	}
    	return 0;
    }