洛谷B3625迷宫寻路

迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 $n\times m$ 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 $(1,1)$ 的位置，问能否走到 $(n,m)$ 位置。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，输入这个迷宫。每行输入一个长为 $m$ 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 $(n,m)$，则输出 Yes；否则输出 No。

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

提示

样例解释

路线如下：$(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)\to (2,3)\to (2,4)\to (2,5)\to (3,5)$

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le 100$，且 $(1,1)$ 和 $(n,m)$ 均为空地。

运用bfs来解决
一开始机器猫在（0，0）位置，要走到（n-1，m-1）位置
边界条件：x、y大于0且分别小于n、m，每一点都只能走一次(通过bool数组记载是否走过)，下一次要走的位置上不是#。

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

int n,m;
const int N = 110;
char path[N][N];
bool st[N][N];
int X[4] = {
   -1,0,1,0};
int Y[4] = {
   0,-1,0,1};


bool bfs()
{
   
    //BFS使用一个队列来存储待访问的节点。
    //队列的特性是先进先出(FIFO)，这确保了BFS是逐层访问节点的。
    queue<pair<int,int>> q;//创建一个队列来存储待访问节点
    q.push({
   0,0});//将起始节点(0,0)入队
    st[0][0] = true;//标记起始节点为已访问

    while(!q.empty())//当队列不为空时，继续搜索
    {
   
        int x = q.front().first;//取出队列中的第一个节点的坐标
        int y = q.front().second;
        q.pop();//弹出队列中的第一个节点

        if(x == n-1 && y == m-1)//如果当前节点是目标节点，则返回 true
        {
   
            return true;
        }

        //遍历当前节点的四个相邻方向
        for(int i = 0;i < 4;i++)
        {
   
            int dx = x + X[i];//计算新节点的 x 坐标
            int dy = y + Y[i];//计算新节点的 y 坐标

            //检查新节点是否在网格范围内、是否未被访问过、以及是否是可通过的节点
            if(dx >= 0 && dy >= 0 && dx < n&& dy < m && !st[dx][dy] && path[dx][dy] != '#')
            {
   
                st[dx][dy] = true;//标记新节点为已访问
                q.push({
   dx,dy});//将新节点加入队列，以便后续访问它的相邻节点
            }
        }
    }
    return false;//如果队列为空且没有找到目标节点，则返回 false
}

int main()
{
   
    cin >> n >> m;

    for(int i = 0;i < n;i++)
    {
   
        for(int j = 0;j < m;j++)
        {
   
            cin >> path[i][j];
            st[i][j] = false;
        }
    }
    if(bfs())
    {
   
        cout << "Yes" <<endl;
    }
    else
    {
   
        cout << "No" <<endl;
    }

    return 0;
}

扩展

获取单一行走路径：

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

int n, m;
const int N = 110;
char path[N][N];
bool st[N][N];
pair<int, int> previous[N][N]; // 用于记录每个节点的父节点
int X[4] = {
   -1, 0, 1, 0};
int Y[4] = {
   0, -1, 0, 1};

bool bfs() {
   
    queue<pair<int, int>> q;
    q.push({
   0, 0});
    st[0][0] = true;

    while (!q.empty()) {
   
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == n - 1 && y == m - 1) {
   
            return true; // 找到目标节点，返回true表示找到路径
        }

        for (int i = 0; i < 4; i++) {
   
            int dx = x + X[i];
            int dy = y + Y[i];

            if (dx >= 0 && dy >= 0 && dx < n && dy < m && !st[dx][dy] && path[dx][dy] != '#') {
   
                st[dx][dy] = true;
                previous[dx][dy] = {
   x, y}; // 记录父节点
                q.push({
   dx, dy});
            }
        }
    }
    return false; // 无法到达目标节点
}

void printPath() {
   
    int x = n - 1, y = m - 1;
    vector<pair<int, int>> path;

    // 回溯到起点，构建路径
    while (x != 0 || y != 0) {
   
        path.push_back({
   x, y});
        pair<int, int> p = previous[x][y];
        x = p.first;
        y = p.second;
    }
    path.push_back({
   0, 0}); // 添加起点

    // 打印路径（从起点到终点）
    for (int i = path.size() - 1; i >= 0; i--) {
   
        cout << "(" << path[i].first << "," << path[i].second << ") ";
    }
    cout << endl;
}

int main() {
   
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
   
        for (int j = 0; j < m; j++) {
   
            cin >> path[i][j];
            st[i][j] = false;
            previous[i][j] = {
   -1, -1}; // 初始化为无效值
        }
    }

    if (bfs()) {
   
        cout << "Yes" << endl;
        printPath(); // 打印路径
    } else {
   
        cout << "No" << endl;
    }

    return 0;
}

在这段代码中，增加了一个previous数组来记录每个节点的父节点。当找到目标节点时，bfs函数返回true，然后调用printPath函数来回溯并打印出从起点到终点的路径。
bfs部分详解：

void printPath() {
     
    int x = n - 1, y = m - 1; // 从终点开始回溯  
    vector<pair<int, int>> path; // 用于存储路径上的节点坐标  
  
    // 回溯到起点，构建路径  
    while (x != 0 || y != 0) {
    // 当还没有回溯到起点时继续循环  
        path.push_back({
   x, y}); // 将当前节点坐标添加到路径中  
        pair<int, int> p = previous[x][y]; // 获取当前节点的父节点坐标  
        x = p.first; // 更新x坐标为父节点的x坐标  
        y = p.second; // 更新y坐标为父节点的y坐标  
    }  
    path.push_back({
   0, 0}); // 添加起点到路径中，因为上面的循环条件导致起点不会被添加  
  
    // 打印路径（从起点到终点），注意这里是从后往前打印，因为路径是从起点开始记录的  
    for (int i = path.size() - 1; i >= 0; i--) {
     
        cout << "(" << path[i].first << "," << path[i].second << ") "; // 打印每个节点的坐标  
    }  
    cout << endl; // 打印换行  
}

printPath 函数是用于打印从起点（0,0）到终点（n-1, m-1）在迷宫中的具体路径的。这个函数通过回溯的方式，利用在广度优先搜索（BFS）过程中记录的每个节点的父节点信息，来重建整条路径。

这个函数的工作流程如下：

1. 初始化终点坐标 (x, y) 为 (n-1, m-1)。
2. 创建一个空的 vector 容器 path，用于存储路径上的节点坐标。
3. 使用 while 循环进行回溯，条件是当前节点不是起点（即 x != 0 || y != 0）。
   • 在循环中，首先将当前节点的坐标 (x, y) 添加到 path 中。
   • 然后，通过查询 prev 数组获取当前节点的父节点坐标，并将父节点坐标赋值给 (x, y)，以便在下一次循环中继续回溯。
4. 循环结束后，将起点坐标 (0, 0) 添加到 path 中，因为回溯过程是从终点开始，到起点结束，但由于循环条件的限制，起点并未被包含在内，所以需要手动添加。
5. 最后，使用 for 循环逆序打印 path 中的节点坐标。这是因为路径在 path 中是以从终点到起点的顺序存储的，而我们需要按照从起点到终点的顺序打印出来。

通过这个函数，我们就可以在控制台上看到从起点到终点的完整路径了。