AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

BFS-走迷宫问题

作者: 作者的头像   ding209696187 ,  2024-08-07 22:36:09 ,  所有人可见 ,  阅读 4


0


#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N], d[N][N];
queue<PII> q;
int n, m;

void bfs(int a, int b) {
    d[0][0] = d[1][1] = 0;
    q.push({a, b});
    while(!q.empty()) {
        PII start = q.front();
        q.pop();
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        for (int i = 0; i < 4; i ++ ) {
            int x = start.first + dx[i], y = start.second + dy[i];
            if (g[x][y] == 0) {
                g[x][y] = 1;
                d[x][y] = d[start.first][start.second] + 1;
                q.push({x, y});
            }
        }
    }
    cout << d[n][m];
}

int main() {
    cin >> n >> m;
    memset(g, 1, sizeof g);
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) cin >> g[i][j];
    }
    bfs(1, 1);
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

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