【广搜BFS】图灵P543. 走出迷宫的最短路径题解

ylch · 2023-07-28 21:20:12 · 个人记录

TURINGOJP543. 走出迷宫的最短路径题解

【猛击这里查看题目】

题目描述

说明

有 n*m 的迷宫，该迷宫有一个入口，一个出口。编写一程序打印一条从迷宫入口到出口的最短路径，黑色方块的单元表示走不通（用 1 表示），白色方块的内容表示走的通（用 0 表示）。

只能往上下左右四个方向走，如果有最短路径，保证最短路径一定是唯一的，如果没有路径可以到达，则输出“no way”。

输入格式

第一行输入 2 个整数 n 和 m(n 和 m 都是 10~150 之间的整数)，代表迷宫的行数和列数接下来 n 行，每行有 m 个整数，1 代表不可走的点，0 代表可走的点。接下来一行，有 2 个整数 s1 和 s2 代表入口的坐标。接下来一行，有 2 个整数 e1 和 e2 代表出口的坐标。

输出格式

输出从入口到出口的最短路径，如果没有路径可达输出“no way”。

样例

输入数据 1

输出数据 1

(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)

思路

其实这道题和其他广搜没什么不同，只是要打印路径。

开始我是这么想的：

我们可以在结构体中新设一个成员 pre，表示上一个位置的结构体，这样当我们找到终点时，就可以用“追根溯源”的方法配合递归函数完成路径打印，类似链表的思想。

因为 C++ 不允许在类中定义本类对象，我们要用类指针，涉及到指针，就会使用动态内存分配、面向对象等复杂的知识，很麻烦，我边学边调了一下午才调出来。

后来理智下来，想一想，其实可以用数组模拟链表，每个结构体里存储前驱下标和当前的坐标，照常按照广搜的模板搜索，找到答案后倒序遍历链表，就求出了答案，比刚开始简单多了。

AC 代码

代码 1

#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#define ll long long
using namespace std;

int n,m,sx,sy,ex,ey;
int a[155][155];
int dis[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };

struct Node
{
    int x,y;    //当前坐标
    int step;   //当前步数
    Node *pre;  //前一个点
};
queue<Node*> que;
int vis[155][155] = {0}; //记录当前步数，方便选择方案

void print(Node *no)
{
    if (no->step == 0)
    {
        printf("(%d,%d)", no->x, no->y);
        return ;
    }
    print(no->pre);
    printf("->(%d,%d)", no->x, no->y);
}

void bfs()
{
    que.push(new Node{sx,sy,0,nullptr});
    vis[sx][sy] = 0;

    while (!que.empty())
    {
        Node *it = que.front(); que.pop();

        if (it->x==ex && it->y==ey)
        {
            print(it);
            exit(0);
        }

        for (int i=0; i<4; i++)
        {
            int tx = it->x + dis[i][0];
            int ty = it->y + dis[i][1];
            if (tx>=1 && tx<=n && ty>=0 && ty<=m && vis[tx][ty]>it->step && !a[tx][ty])
            {
                que.push(new Node{tx,ty,it->step+1,it});
                vis[tx][ty] = it->step;
            }
        }

    }
}

signed main()
{
    memset(vis, 0x3f, sizeof vis); //初始为最大值
    scanf("%d %d", &n, &m);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
            scanf("%d", &a[i][j]);
    }
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);

    bfs();

    printf("no way\n");
    return 0;
}

代码 2

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

int n,m,i,j;
int a[155][155];
int fx[5] = {0, 0, 1, 0, -1};
int fy[5] = {0, 1, 0, -1, 0};
int tx,ty;
struct Info
{
    int x,y; //坐标
    int pre,cur; //前驱节点下标、当前下标
};
Info track[400010];
int s1,s2,e1,e2,cnt;
queue<Info> q;

void print(int k)
{
    if (track[k].pre != 0)
        print(track[k].pre);
    cout << "(" << track[k].x << "," << track[k].y << ")";
    if (k != cnt)   cout << "->";
}

int main()
{
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
            cin >> a[i][j];
    }
    cin >> s1 >> s2 >> e1 >> e2;
    a[s1][s2] = 1;
    track[++cnt] = (Info){s1,s2,0};
    q.push((Info){s1,s2,0,cnt});

    while (!q.empty())
    {
        int pos = q.front().cur;
        for (i=1; i<=4; i++)
        {
            tx = q.front().x + fx[i];
            ty = q.front().y + fy[i];
            if (tx>=1 && tx<=n && ty>=1 && ty<=m && !a[tx][ty])
            {
                track[++cnt] = (Info){tx,ty,pos};
                q.push((Info){tx,ty,pos,cnt});
                a[tx][ty] = 1;
                if (tx==e1 && ty==e2)
                {
                    print(cnt);
                    return 0;
                }
            }
        }
        q.pop();
    }
    cout << "no way" << endl;
    return 0;
}

End

谢谢大家！掰掰ヾ(•ω•`)o

【广搜BFS】图灵P543. 走出迷宫的最短路径 题解

TURINGOJP543. 走出迷宫的最短路径 题解