【蓝桥杯 2019初赛 C/C++大学A组】迷宫(bfs模板)

题目链接http://oj.ecustacm.cn/problem.php?id=1455

1 题目

题目描述

下图给出了一个迷宫的平面图,其中标记为 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

2 题解

#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;
}