AcWing 1076. 迷宫问题

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1076. 迷宫问题原题链接简单

作者：

黄亦玫 , 2019-11-27 11:50:26 , 所有人可见 , 阅读 7055

28

6

算法1

BFS

其他的都很好理解，就是我写的时候有一个问题，找了好久最后找到啦~~
就是在打印路线的时候我直接用原来的变量进行更新的就比如我用
en.x = tath[en.x][en.y].x; （1）
en.y = path[en.x][en.y].y; （2）

看着没有问题，但其实在1式中end.x已经被更新了，我却用这个已经被更新的变量去更新上一次还未更新的en.y所以答案肯定就错误啦~~，因此需要把变量保存下来，然后用上一次的变量去更新这一次的值。

时间复杂度

参考文献

C++ 代码

#include <queue>
#include <iostream>
#include <algorithm>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;

int g[N][N];
PII memory[N][N];

int st[N][N];
int n;

void bfs()
{
    queue<PII> q;
    q.push({n - 1,  n - 1});
    st[n - 1][n - 1] = true;
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++)
        {
            int x = dx[i] + t.x, y = dy[i] + t.y;
            if(x < 0 || x >= n || y < 0 || y >= n)continue;
            if(st[x][y])continue;
            if(g[x][y] == 1)continue;
            q.push({x, y});
            st[x][y] = true;
            memory[x][y] = t;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];
    bfs();
    PII end = {0, 0};
    cout << 0 << ' ' << 0 << endl;

    while(end.x != n - 1 || end.y != n - 1)
    {
        printf("%d %d\n", memory[end.x][end.y].x, memory[end.x][end.y].y);
        int x = end.x, y = end.y;
        end.x = memory[x][y].x, end.y = memory[x][y].y;
    }

    return 0;
}

24 评论

ff_z98 2022-08-20 23:02

麻烦问下如果起点不固定为(0,0)，应该如何考虑呢

baobaojiao 2022-11-06 21:23

如果起点为x1, y1;
auto t = q.front();
q.pop();
if(p.x == x1 && p.y == y1)return;

kimihiki 11个月前

大佬们，怎么回事后面几个数据一直Segmentation Fault

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n,m,tim;
int g[N][N],d[N][N];
PII q[N * N],pre[N][N],ans[N];

int bfs(){
    int hh = 0,tt = 0;
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
    q[0] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;
    while(hh <= tt){
        auto t = q[hh ++];
        for(int i = 0; i < 4; i ++){
            int x = t.first + dx[i];
            int 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;
                pre[x][y] = t;
                q[++ tt] = {x,y};
            }

        }
    }
    //倒序输出路径
    int x = n - 1,y = m - 1;
    while(x || y){
        //  cout << x << " " << y << endl;
        ans[tim ++] = {x,y};
        auto t = pre[x][y];
         x = t.first,y = t.second;
    }
    return d[n - 1][m - 1];
}
int main(){
    scanf("%d",&n);
    m = n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m;j  ++)
            scanf("%d",&g[i][j]);

    bfs();
    cout << "0 0" << endl;
    for(int i = tim - 1; i >= 0; i --)cout << ans[i].first << " " << ans[i].second << endl;
    // printf("%d\n",bfs());
    return 0;
}