AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

2019年蓝桥杯迷宫问题

作者: 作者的头像   心在远方_ ,  2023-03-19 20:18:36 ,  所有人可见 ,  阅读 54


0


#include <iostream>
#include <cstring>
using namespace std;

const int N = 70;
int m,n;
char x[N][N];
int y[N][N];
pair<int,int> w[N * N],q[N][N],e[N * N];
char ss[N * N];

void bfs(){
    memset(y,-1,sizeof y);
    y[1][1] = 0;
    int h = 1,k = 1;
    w[1] = {1,1};
    int dx[] = {1,0,0,-1};
    int dy[] = {0,-1,1,0};
    while(h <= k){
        auto qq = w[h ++];
        for (int i = 0; i <= 3; i ++ ) {
            int xx = qq.first + dx[i];
            int yy = qq.second + dy[i];
            if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && y[xx][yy] == -1 && x[xx][yy] == '0'){
                y[xx][yy] = y[qq.first][qq.second] + 1;
                q[xx][yy] = qq;
                w[++ k] = {xx,yy};
            }
        }
    }
    int x1 = m,y1 = n;
    int u = 0;
    while(x1 != 1 || y1 != 1){
        u ++;
        // cout << x1 << " " << y1 << endl;
        e[u].first = x1;
        e[u].second = y1;
        auto pp = q[x1][y1];
        x1 = pp.first;
        y1 = pp.second;
    }
    u ++;
    e[u].first = 1;
    e[u].second = 1;
    for(int i = u - 1;i >= 1; i -- ){
        if(e[i].first - e[i + 1].first == 1) cout << "D";
        if(e[i].first - e[i + 1].first == -1) cout << "U";
        if(e[i].second - e[i + 1].second == 1) cout << "R";
        if(e[i].second - e[i + 1].second == -1) cout << "L";
    }
}

int main(){
    scanf("%d %d\n",&m,&n);
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) scanf("%c",&x[i][j]);
        scanf("\n");
    }
    // for (int i = 1; i <= m; i ++ ) {
    //     for (int j = 1; j <= n; j ++ ) printf("%c ",x[i][j]);
    //     printf("\n");
    // }
    bfs();
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息