宁夏石嘴山市城乡建设局提意见网站,保洁公司哪家好,专门做租房的网站,北京网页网站设计制作题目#xff1a; 问题描述学霸抢走了大家的作业#xff0c;班长为了帮同学们找回作业#xff0c;决定去找学霸决斗。但学霸为了不要别人打扰#xff0c;住在一个城堡里#xff0c;城堡外面是一个二维的格子迷宫#xff0c;要进城堡必须得先通过迷宫。因为班长还有妹子要陪…题目 问题描述学霸抢走了大家的作业班长为了帮同学们找回作业决定去找学霸决斗。但学霸为了不要别人打扰住在一个城堡里城堡外面是一个二维的格子迷宫要进城堡必须得先通过迷宫。因为班长还有妹子要陪磨刀不误砍柴功他为了节约时间从线人那里搞到了迷宫的地图准备提前计算最短的路线。可是他现在正向妹子解释这件事情于是就委托你帮他找一条最短的路线。
输入格式第一行两个整数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
110Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRDOutput Sample 2:
4
DDRR
数据规模和约定有20%的数据满足1n,m10有50%的数据满足1n,m50有100%的数据满足1n,m500。 解题思路 这个题是典型的BFS路径问题通过BFS即可获得最短路径长度再通过寻找父节点的方式获得路径。 #include stdio.hstruct node{int x;int y;int s;int d;int p;
}; int main(){char map[501][501], path[2500] ;//此处为了方便设定了一个固定值如果想节约内存空间可以动态增加 int book[501][501] {0};int n, m, head 1, tail 1, flag 0;struct node que[2501];int next[4][3] {{-1, 0, U},//上U {1, 0, D},//下D{0, -1, L},//左L{0, 1, R}//右R};int i, j,tx, ty;scanf(%d %d, n, m);for(i 0; i n; i){scanf(%s, map[i]);}que[tail].x 1;que[tail].y 1;que[tail].s 0;que[tail].p 0;tail;book[1][1] 1;while(head tail){if(flag){break;}for(i 0; i 4; i){tx que[head].x next[i][0];ty que[head].y next[i][1];if(tx 1 || ty 1 || tx n || ty m){continue;} if(book[tx][ty] 0 map[tx - 1][ty - 1] 0){book[tx][ty] 1;que[tail].x tx;que[tail].y ty;que[tail].s que[head].s 1;que[tail].d next[i][2];que[tail].p head; tail; }if(tx n ty m){flag 1;break;}}head;}i tail - 1;j 0;while(que[i].p ! 0){path[j] que[i].d;i que[i].p;}//输出结果 printf(%d\n, que[tail - 1].s);for(j--; j 0; j--){printf(%c, path[j]);}return 0;
} 在此感谢“T.H”提供的测试数据。 博客名称王乐平博客 博客地址http://blog.lepingde.com CSDN博客地址http://blog.csdn.net/lecepin
