题目
下图给出了一个迷宫的平面图,其中标记为1 的为障碍,标记为0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫,
一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫(30 行50 列),请找出一种通过迷宫的方式,
其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。
思路
迷宫类很容易想到使用 dfs 来搜索,虽然学过,但还是花了不少时间。
有几个注意点:
代码
//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;
}