题目链接:http://oj.ecustacm.cn/problem.php?id=1455
下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。
010000 000100 001001 110000
迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这个它的上、下、左、右四个方向之一。
对于上面的迷宫,从入口开始,可以按 DRRURRDDDR 的顺序通过迷宫,一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫( 30 行 50 列),请找出一种通过迷宫的方式,其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为案。
请注意在字典序中 $D<L<R<U$。
见文件:http://oj.ecustacm.cn/upload/file/20200122/20200122134020_61830.txt
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 60;
char mp[maxn][maxn];
int vis[maxn][maxn] = {0};
int dir[4][2] = {
{1,0}, {0, -1}, {0,1}, {-1,0}};
char dirc[4] = {'D', 'L', 'R', 'U'};
int n, m;
struct node{
int x, y, step;
string s;
node(int xx, int yy, int sstep, string ss){
x = xx;
y = yy;
step = sstep;
s = ss;
}
};
queue<node> q;
bool check(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] == 1 || mp[x][y] == '1'){
return false;
}
return true;
}
void bfs(int x, int y){
q.push(node(x, y, 0, ""));
vis[x][y] = 1;
while(!q.empty()){
node now = q.front();
if(now.x == n - 1 && now.y == m - 1){
cout << now.s << endl;
cout << now.step << endl;
break;
}
q.pop();
for(int i = 0;i < 4;i++){
int nx = now.x + dir[i][0];
int ny = now.y + dir[i][1];
if(check(nx, ny)){
q.push(node(nx, ny, now.step + 1, now.s + dirc[i]));
vis[nx][ny] = 1;
}
}
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif //ONLINE_JUDGE
cin >> n >> m;
for(int i = 0;i < n;i++){
cin >> mp[i];
}
bfs(0, 0);
return 0;
}