问题描述
学霸抢走了大家的作业, 班长为了帮同学们找回作业, 决定去找学霸决斗但学霸为了不要别人打扰, 住在一个城堡里, 城堡外面是一个二维的格子迷宫, 要进城堡必须得先通过迷宫因为班长还有妹子要陪, 磨刀不误砍柴功, 他为了节约时间, 从线人那里搞到了迷宫的地图, 准备提前计算最短的路线可是他现在正向妹子解释这件事情, 于是就委托你帮他找一条最短的路线
输入格式
第一行两个整数 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
一道简单的广搜题目, 对我来说广搜找到最短路不是太难, 但是路径的记录有点难
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <queue>
- #define N 550
- using namespace std;
- struct node
- {
- int x, y;
- int num;
- };
- int n, m;
- char map[N][N];
- int vis[N][N];
- int dir[4][2] = {1, 0, 0, -1, 0, 1, -1, 0};
- int pre[N][N];
- char str[5] = {"DLRU"};
- bool check(int x,int y)
- {
- if(x<1||x>n||y<1||y>m)
- return false;
- return 1;
- }
- void bfs()
- {
- queue <node> q;
- node st;
- st.x = 1, st.y = 1, st.num = 0;
- q.push(st);
- vis[1][1] = 1;
- pre[1][1] = -1;
- while(!q.empty())
- {
- st = q.front();
- q.pop();
- if(st.x == n && st.y == m)
- {
- printf("%d\n", st.num);
- return ;
- }
- int i, j;
- node ed;
- for(i = 0; i < 4; i++)
- {
- ed.x = st.x + dir[i][0];
- ed.y = st.y + dir[i][1];
- ed.num = st.num + 1;
- if(check(ed.x,ed.y)&& map[ed.x][ed.y] == 0 && !vis[ed.x][ed.y])
- {
- pre[ed.x][ed.y] = i;
- q.push(ed);
- vis[ed.x][ed.y] = 1;
- }
- }
- }
- }
- void path(int x, int y)
- {
- if(x == 1 && y == 1) return;
- path(x - dir[pre[x][y]][0], y - dir[pre[x][y]][1]);
- printf("%c", str[pre[x][y]]);
- }
- int main ()
- {
- scanf("%d %d", &n, &m);
- int i, j;
- for(i = 1; i <= n; i++)
- {
- for(j = 1; j <= m; j++)
- {
- scanf("%c", &map[i][j]);
- }
- getchar();
- }
- bfs();
- path(n, m);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2501685.html