蓝桥杯算法提高学霸的迷宫（bfs+路径记录）

小咪咪 2024-02-17 19:40 5阅读 0赞

算法提高 学霸的迷宫

时间限制：1.0s 内存限制：256.0MB

问题描述

学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入格式

第一行两个整数n， m，为迷宫的长宽。  
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式

第一行一个数为需要的最少步数K。  
　　第二行K个字符，每个字符∈\{U,D,L,R\},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

Input Sample 1:  
3 3  
001  
100  
110  
  
Input Sample 2:  
3 3  
000  
000  
000

样例输出

Output Sample 1:  
4  
RDRD  
  
Output Sample 2:  
4  
DDRR

数据规模和约定

有20%的数据满足：1<=n,m<=10  
　　有50%的数据满足：1<=n,m<=50  
　　有100%的数据满足：1<=n,m<=500。

思路：bfs+路径记录

题目要求：如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个，处理方法就是按照 D、L、R、U的顺序循环即可’

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn=500+2;
    int n,m;
    char g[maxn][maxn];
    char p[maxn][maxn];  //路径操作 
    int d[maxn][maxn];
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    };
    node path[maxn][maxn];  //保存路径节点 
    int dir[][2]={
       {1,0},{0,-1},{0,1},{-1,0}};
    
    bool isValid(node& nd){
    	return nd.x>=1&&nd.x<=n && nd.y>=1&&nd.y<=m;
    }
    
    void print(node &nd){  //打印路径 
    	vector<char> vec; 
    	node u=nd;
    	while(d[u.x][u.y]){
    		vec.push_back(p[u.x][u.y]);
    		u=path[u.x][u.y];
    	}
    	
    	for(int i=vec.size()-1;i>=0;i--){
    		printf("%c",vec[i]);
    	}
    	printf("\n");
    }
    void bfs(){
    	memset(d,-1,sizeof(d));
    	queue<node>q;
    	q.push(node(1,1));
    	d[1][1]=0;
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(u.x==n && u.y==m){
    			printf("%d\n",d[n][m]);
    			print(u);
    		}
    		
    		for(int i=0;i<4;i++){
    			node v=node(u.x+dir[i][0],u.y+dir[i][1]);
    			if(isValid(v) && g[v.x][v.y]=='0' && d[v.x][v.y]==-1){
    			q.push(v);
    			d[v.x][v.y]=d[u.x][u.y]+1;
    			path[v.x][v.y]=u;
    			if(dir[i][0]==1 && dir[i][1]==0)
    			p[v.x][v.y]='D';
    			else if(dir[i][0]==0 && dir[i][1]==-1)
    			p[v.x][v.y]='L';
    			else if(dir[i][0]==0 && dir[i][1]==1)
    			p[v.x][v.y]='R';
    			else if(dir[i][0]==-1 && dir[i][1]==0)
    			p[v.x][v.y]='U';
    		}
    	}
    }
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=1;i<=n;i++)
    		 scanf("%s",g[i]+1);
    		bfs();	
    	} 
    	return 0;
    }