AcWing 844. 走迷宫

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 844. 走迷宫原题链接简单

作者：

捡到一束光 , 2019-07-14 12:48:16 , 所有人可见 , 阅读 28227

132

121

问题1：走迷宫——边的权值相同

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

样例

输出样例：
8

算法

(BFS)

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e2 + 7;
int g[N][N], d[N][N];
int n, m;


int bfs() {
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    queue <PII> q;

    for (auto &v : d) 
        for (auto &x : v) {
            x = - 1;
        }

    d[0][0] = 0;
    q.push({0, 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];

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

    }


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

问题2:走迷宫升级版——边的权值不同

单点时限: 2.0 sec
内存限制: 256 MB
一天，sunny 不小心进入了一个迷宫，不仅很难寻找出路，而且有的地方还有怪物，但是 sunny 有足够的能力杀死怪物，但是需要一定的时间，但是 sunny 想早一点走出迷宫，所以请你帮助他计算出最少的时间走出迷宫，输出这个最少时间。

我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口，则输出 impossible. 每次走只能是上下左右 4 个方向。

输入格式
每次首先 2 个数 n,m (0<n,m≤200)，代表迷宫的高和宽，然后 n 行，每行 m 个字符。

S 代码你现在所在的位置。
T 代表迷宫的出口。
# 代表墙，你是不能走的。
X 代表怪物。
. 代表路，可以走。
处理到文件结束。

输出格式
输出最少的时间走出迷宫。不能走出输出 impossible。

样例

输入样例：
4 4
S.X.
#..#
..#.
X..T
4 4
S.X.
#..#
..#.
X.#T

输出样例：
6
impossible

算法

(BFS + 优先队列)

题意：走迷宫，求最短路径，上下左右走一格花费1，走到有怪的格子花费2.

思路：将每一点的坐标和由起点到该点的距离存入结构体.
由起点开始，将该点存入优先队列，以到起点的距离dis为优先级，每次取出dis最小的，向外扩散。
相当于第一轮得出所有到起点距离为1的点，第二轮得出所有到起点距离为2的点。
注意：对普通的最短路问题，由于每个各自的花费相同，因此每次存入的点优先级都相同.
故不需要使用优先队列，但本题存在有无怪物的区别，每次存入的格子的优先级可能不同，故使用优先队列。

C++ 代码


#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
char maze[201][201];
int sx, sy, tx, ty;
//左右上下4个方向
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int m, n;

struct node {
    int x,  y, dis;
};

bool operator < (const node & a, const node & b) {
    return a.dis > b.dis;
}

void bfs() {
    priority_queue<node> que;
    node st { sx,sy,0 };
    maze[sx][sy] = '#';
    que.push(st);

    while (!que.empty()) {
        node p = que.top();
        que.pop();
        //若已找到，则退出
        if (p.x == tx && p.y == ty) {
            cout << p.dis << endl;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            node np{ nx,ny, 0};

            if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&maze[nx][ny] != '#') {
                if (maze[nx][ny] == 'X')
                    np.dis = p.dis + 2;
                else
                    np.dis = p.dis + 1;
                maze[np.x][np.y] = '#';
                que.push(np);

            }
        }
    }
    printf("impossible\n");
}
int main() {
    while (cin>>n>>m) {
        for (int i = 0; i < n; i++)
            scanf("%s", maze[i]);
        for(int i=0; i<n; i++)
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == 'S')
                    sx = i, sy = j;
                else if (maze[i][j] == 'T')
                    tx = i, ty = j;
            }
        bfs();
    }
    return 0;
}

43 评论

TYUT_不知名选手 2022-10-14 20:03

很厉害！走过一个点之后这个点就变成墙了！

Think_brid 2022-09-30 16:36

大佬tql

xiao_ma 2022-10-04 10:18

用优先队列的意义是啥呢？不太懂

xiao_ma 2022-10-04 10:20

利用小根堆？每次都取堆顶，是贪心的思想吗？

卷毛狒狒 2023-02-28 17:50

实际上就是迪杰斯特拉

Ησυνείδησητης 6个月前回复了 xiao_ma 的评论

我感觉像是每次都先走离当前节点距离最近的节点，满足最小这个特点。就是当图中同一个节点连着多个节点，先选取最小的点进行遍历，进队列，

h闵 7个月前

#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];这样才可以啊，我不理解这个是为什么，原则上不都是可以的吗?

y总保佑我nobug 2023-02-15 11:34

我感觉不能理解为什么输出是最小值
按理说最大值应该会最后输出，然后覆盖掉，除非在while中间判断终点break掉，但是结果就是最小值

炸掉地球 2023-03-23 16:09

因为d[x][y]赋过值后就不再更新了，所以每次是最优解，不会再访问了

rick_2 2022-07-14 11:15

大佬，tql

arni1mo 2022-06-13 10:42

求问一下，这里是小顶堆还是大顶堆？priority_queue默认less是大顶堆，这里重写了node的比较函数，是堆顶元素存放的是dis小的吗？

南岸以南南岸哀 2022-06-30 21:47

默认greater 顶是最小的堆

Mr.lonely_6 2021-12-07 14:36

for(int i = 0;i < 4;i++) {
int nx = t.first + dx[i], ny = t.second + dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 0 && d[nx][ny] == -1) { // d[x][y]==-1 表示这个点没有标记过
d[nx][ny] = d[t.first][t.second] + 1; // 距离+1
q.push({nx,ny});
if(nx == n && ny == m) return d[nx][ny]; // 提前返回
}
}

// 这里为什么不要提前返回？到了终点就推出，为什么还继续，继续的话答案不会更大嘛

Mr.lonely_6 2021-12-07 14:41

如果终点已经遍历到了，队列中还有点，但是无法更新终点的d距离了

正能量的阿龙 2022-02-16 16:08 回复了 Mr.lonely_6 的评论

因为用d数组保存了拓展到该点时走的步数，即使不提前返回，遍历完所有的点，也不会出错，因为每个点都只遍历了一次

xty 2022-07-16 10:54

d[x][y]会标记每次经过的点（d[x][y]!=-1则不会遍历这个点），那么每个点只会被遍历一次。由于bfs是一层一层搜索的，那么如果存在一条最短路，它一定会先于其他路径被遍历到，且由于每个点只会被遍历一次，所以终点的d[x][y]存的就是唯一的最短路。至于题解中另一题加了个提前返回只是写法不同，你也可以不加那个if让他有个返回值，如果返回值是0则输出“impossible”

偷走牛油果 2021-07-18 11:25

for (auto &v : d)
for (auto &x : v) {
x = - 1;
}
这段是干嘛的呀

捡到一束光 2021-07-19 12:09

初始化数组

RussellWoo 2022-08-26 15:01 回复了捡到一束光的评论

请问是初始化的d[N][N]状态数组吗

江水灬之畔 8个月前

https://www.acwing.com/solution/content/238335/ 分析一下如何利用BFS进行迷宫走路径的过程，并且附带打印输出走过的路径的代码。希望可以帮到大家

DKH 2023-02-01 20:39

d[x][y] = d[t.first][t.second] + 1;不太懂这句, 哪位大佬能解释下

金钱豹非洲分豹 2023-01-12 21:23

woc这算法好明白

Pobz 2023-01-08 19:52

www怎么才能像你一样厉害

予耄逊于荒 2022-09-13 22:32

#include <bits/stdc++.h>
using namespace std;
int bfs(vector<vector<int>> vec, vector<vector<int>> g) {
  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  queue<pair<int, int>> q;
  q.push({0, 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];
      if (x >= 0 && x < vec.size() && y >= 0 && y < vec[0].size() &&
          !g[x][y] && !vec[x][y]) {
        vec[x][y] = vec[t.first][t.second] + 1;
        q.push({x, y});
      }
    }
  }
  return vec[g.size() - 1][g[0].size() - 1];
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n, vector<int>(m, -1));
  vector<vector<int>> vec(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> g[i][j];
  cout << bfs(vec, g) << endl;
}