1455: [蓝桥杯2019初赛]迷宫
题目
下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。
思路
迷宫类很容易想到使用 dfs 来搜索，虽然学过，但还是花了不少时间。
有几个注意点：
- 这里需要记录最短路径，因此 dfs 同时要用一个 steps 变量来保存当前步数；并且当到达终点（即x = 30, y = 50）时，与最短步数比较，若大于最短步数，则作废。
- 由于最后输出的时每一步的操作（D, P, L, R），因此可以使用数组先保存对应操作，到终点时统一拼接成字符串即可。
- 采用剪枝操作。dp 数组记录了从七点到每一点（x, y）的最短路径，若访问该点时，steps已超过起点到该点的最短路径，说明当前并不是最优，return。
代码
//1455: [蓝桥杯2019初赛]迷宫
#include<iostream>
using namespace std;
string ans; //保存答案
bool vis[40][60]; //是否访问过
int map[40][60]; //保存地图
int minn = 999999; //保存最短路steps
int add[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; //D<L<R<U
int dp[40][60]; //保存每一步的当前路数
int vv[99999]; //保存操作，方便转换
char s[5] = {'D', 'D', 'L', 'R', 'U'}; //从1开始
void dfs(int x, int y, int steps){
if(steps > minn)
return;
if(x == 30 && y == 50){
if(steps < minn){
minn = steps;
string tmp;
for(int i = 1; i < steps; i++){
tmp += s[vv[i]];
}
ans = tmp;
}
return;
}
for(int i = 1; i <= 4; i++){
//四个循环
int tx = x + add[i-1][0];
int ty = y + add[i-1][1];
if(tx < 1 || ty < 1 || tx > 30 || ty > 50) //越界
continue;
if(vis[tx][ty] || map[tx][ty] == 1) //障碍物或者重复访问
continue;
if(steps + 1 > dp[tx][ty])
return;
dp[tx][ty] = steps + 1; //到达tx，ty这点的路径目前是最短的
vis[tx][ty] = 1; //标记已经访问过了
vv[steps] = i; //当前选择了哪一个操作
dfs(tx, ty, steps + 1);
vis[tx][ty] = 0;
}
}
int main(){
//初始化dp
for(int i = 1; i <= 30; i++){
for(int j = 1; j <= 50; j++){
dp[i][j] = 999999;
}
}
//读入地图
for(int i = 1; i <= 30; i++){
for(int j = 1; j <= 50; j++){
map[i][j] = (getchar() - '0');
}
getchar(); //换行符
}
vis[1][1] = 1;//标记起点
dfs(1, 1, 1);
cout << ans;
return 0;
} 本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读