算法提高-学霸的迷宫

算法提高学霸的迷宫时间限制：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},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。样例输入InputSample1:33001100110InputSample2:33000000000样例输出OutputSample1:4RDRDOutputSample2:4DDRR数据规模和约定有20%的数据满足：1=n,m=10有50%的数据满足：1=n,m=50有100%的数据满足：1=n,m=500。要点分析：经典的广度优先遍历对每个位置保存所走过的步骤和轨迹对各种的排序问题可以通过设置方向为增序即可，也就是D,L,U,R#includeiostream#includecstdio#includecstring#includecmath#includequeue#includestringusingnamespacestd;chara[505][505];intdr[4][2]={1,0,0,-1,0,1,-1,0};chardr_c[5]={'D','L','R','U'};//intvst[505][505];structnodes{intx;inty;intnum_ans;stringans;nodes(inti,intj){x=i;y=j;num_ans=0;ans=;}};queuenodesq;intmain(){intn,m;scanf(%d%d,&n,&m);memset(a,0,sizeof(a));//memset(vst,0,sizeof(vst));inti,j;getchar();//strings;for(i=0;in;i++){/*getline(cin,s);for(j=0;jm;j++){a[i][j+1]=s[j]-'0';}*/cina[i];getchar();}/*for(i=0;in;i++){for(j=0;jm;j++){printf(%c,a[i][j]);}printf(\n);}*/nodesstart(0,0);nodestmp(0,0);nodesnow(0,0);q.push(start);intmx,my;while(!q.empty()){now=q.front();q.pop();if(now.x==n-1&&now.y==m-1){break;}for(i=0;i4;i++){tmp.x=now.x+dr[i][0];tmp.y=now.y+dr[i][1];tmp.num_ans=now.num_ans+1;tmp.ans=now.ans+dr_c[i];mx=tmp.x;my=tmp.y;if(mx=0&&mxn&&my=0&&mym&&a[mx][my]!='1'){q.push(tmp);a[tmp.x][tmp.y]='1';}}}coutnow.num_ansendl;coutnow.ansendl;return0;}技巧：迷宫的存储、输入的设置设置arr为字符串数组时，可书写程序如下：1.for(inti=1;i=m;i++){2.for(intj=1;j=n;j++){3.scanf(%1d,&arr[i][j]);4.}5.}