AcWing 844. 走迷宫(C++详细注释)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 844. 走迷宫(C++详细注释) 原题链接简单

作者：

Shimmers微光 , 2021-07-19 15:17:28 , 所有人可见 , 阅读 4219

58

23

题目注意点

由于任意两个相邻的点的距离权值都为1, 所以d[][]存储的是其他点到源点的最短距离,也即用BFS求出的是最少移动次数

C++ 代码

#include <iostream>
#include <queue>        //使用队列的需要用的头文件
#include <cstring>      //使用memset()需要用到的头文件
using namespace std;

typedef pair<int, int> PII; //定义坐标的数据结构

const int N = 110;

int n, m;
int g[N][N];    //记录地图信息
int d[N][N];    //记录每个顶点到源点的距离

int bfs() {
    queue<PII> q;   //定义一个坐标队列
    q.push({0,0});  //源点进队

    memset(d, -1, sizeof d);    //初始化各个点到源点的距离为-1
    d[0][0] = 0;                //源点到自己的距离为0

    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};     //向四个方向扩展的坐标数组(个人按照[上右下左]的顺序)

    while(!q.empty()) {
        auto t = q.front();     //取队头元素
        q.pop();                //队头元素出队

        for(int i = 0; i < 4; i++) {    //分别向四个方向扩展
            int x = t.first + dx[i], y = t.second + dy[i];  //扩展后的坐标
            //首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)
            //最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[t.first][t.second] + 1; //更新未被访问的点到源点的距离
                q.push({x,y});                      //(x,y)进队
            }
        }
    }
    return d[n-1][m-1];     //返回右下角元素到源点的距离
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];     //读入地图信息
    cout << bfs() << endl;
    return 0;
}

27 评论

lxk_ 2022-10-27 21:07

队的作用是什么

h闵 9个月前

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
// #include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int g[N][N];
int d[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int n,m;

// vector<PII> q;
PII q[N * N];

int dfs()
{
    int hh = 0,tt = 0;
    q[hh] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;

    while(hh <= tt)
    {
        PII t = q[hh];
        hh++;

        for(int i = 0;i < 4;i++)
        {
            int x = t.first + dx[i],y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }

    printf("%d\n",dfs());

    return 0;
}

为什么vector[HTML_REMOVED] q;就会报错
PII q[N * N];这样才可以啊，我不理解这个是为什么，原则上不都是可以的吗?

jack_152 11个月前

orz，看了y总讲解和高赞题解没看懂，看这个终于看懂了[哭]

Wzxc 2022-07-07 23:31

题主注释yyds

aiRR 2023-03-04 21:31

佬q.push({x,y}); 让它入队的含义是什么呀

Wzxc 2023-03-05 09:29 回复了 aiRR 的评论

你模拟一下就明白了。让新点入队才能继续搜下去啊，不断新点入队往后搜索才能找到到终点的最小路径

aiRR 2023-03-05 09:50 回复了 Wzxc 的评论

ok，懂了，感谢佬

Winslow 2022-01-25 09:27

感谢分享，帮我把零碎的理解串联起来了

Camellia_15 12天前

怎么保证是最短路径的啊？

Gpd001 2023-10-12 20:08

请问一下，为什么我的把代码改一下就少了一个？
具体代码

#include <bits/stdc++.h>
using namespace std;
int n, m, hh = 1, tt = 1, num[10010], d[110][110];
bool g[110][110];
int bfs(){
    num[tt ++] = 0;
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
    //向四个方向扩展的坐标数组(个人按照[上右下左]的顺序)
    while(hh <= tt) {
        int tx = num[hh] % 100, ty = num[hh] / 100;  //取队头元素
        hh ++;   //队头元素出队
        for(int i = 0; i < 4; i++) {    //分别向四个方向扩展
            int x = tx + dx[i], y = ty + dy[i];  //扩展后的坐标
            //首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)
            //最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[tx][ty] + 1; //更新未被访问的点到源点的距离
                num[tt ++] = y * 100 + x;      //(x,y)进队
            }
        }
    }
    return d[n-1][m-1];     //返回右下角元素到源点的距离
}
int main(){
    scanf ("%d%d", &n, &m);
    for (int i = 0;i < n;i ++)
        for (int j = 0;j < m;j ++)
            scanf ("%d", &g[i][j]), d[i][j] = -1;
    bfs();
    for (int i = 0;i < n;i ++){
        for (int j = 0;j < m;j ++)
            printf ("% 5d ", d[i][j]);
        printf ("\n");
    }
    return 0;
}

//具体步数
1 -1 5 6 7
0 -1 4 -1 6
1 2 3 4 5
2 -1 -1 -1 6
3 4 5 -1 7