《算法提高-学霸的迷宫》由会员分享，可在线阅读，更多相关《算法提高-学霸的迷宫（6页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上算法提高 学霸的迷宫 时间限制：1.0s 内存限制：256.0MB问题描述学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。输入格式第一行两个整数n， m，为迷宫的长宽。接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标
2、(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。输出格式第一行一个数为需要的最少步数K。第二行K个字符，每个字符U,D,L,R,分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。样例输入Input Sample 1:3 3001100110Input Sample 2:3 3000000000样例输出Output Sample 1:4RDRDOutput Sample 2:4DDRR数据规模和约定有20%的数据满足：1=n,m=10有50
3、%的数据满足：1=n,m=50有100%的数据满足：1=n,m=500。要点分析：经典的广度优先遍历 对每个位置保存所走过的步骤和轨迹 对各种的排序问题可以通过设置方向为增序即可，也就是D,L,U,R#include iostream#include cstdio#include cstring#include cmath#include queue#include stringusing namespace std;char a505505;int dr42=1,0,0,-1,0,1,-1,0;char dr_c5=D,L,R,U;/int vst505505;struct nodesint
4、 x;int y;int num_ans;string ans;nodes(int i,int j)x=i;y=j;num_ans=0;ans=;queue q;int main()int n,m;scanf(%d%d,&n,&m);memset(a,0,sizeof(a);/memset(vst,0,sizeof(vst);int i,j;getchar();/string s;for(i=0;in;i+)/*getline(cin,s);for(j=0;jai;getchar();/*for(i=0;in;i+)for(j=0;jm;j+)printf(%c ,aij);printf(n)
5、; */nodes start(0,0);nodes tmp(0,0);nodes now(0,0);q.push(start);int mx,my;while(!q.empty()now=q.front();q.pop();if(now.x=n-1&now.y=m-1)break;for(i=0;i=0&mx=0&mym&amxmy!=1)q.push(tmp);atmp.xtmp.y=1;coutnow.num_ansendl;coutnow.ansendl;return 0;技巧：迷宫的存储、输入的设置设置arr为字符串数组时，可书写程序如下：1. for(inti=1;i=m;i+)2. for(intj=1;j=n;j+)3. scanf(%1d,&arrij);4. 5. 专心-专注-专业
