C++迷宫求解程序：如何按正确顺序显示路径？

核心问题 #

你当前的遍历方式是行优先遍历数组（从上到下、从左到右），这只能输出数组中标记为1的坐标，但无法体现迷宫路径的行走顺序（从入口到出口的移动轨迹）。要得到正确顺序，需要追踪路径的行走过程，而不是事后遍历数组。

解决方案 #

方法1：求解过程中直接记录路径（推荐） #

在迷宫求解的回溯/搜索过程中，每确定一步是有效路径时，就将坐标存入一个顺序容器（比如vector<pair<int, int>>）。回溯时移除当前坐标，最终找到出口时，容器内的顺序就是正确的路径顺序。

示例代码：

#include <vector>
#include <iostream>
using namespace std;

vector<pair<int, int>> path;
int rows, cols;
// 假设出口坐标为 (exit_i, exit_j)，入口为 (start_i, start_j)

bool solveMaze(int maze[][10], int sol[][10], int i, int j, int exit_i, int exit_j) {
    // 到达出口，输出路径
    if (i == exit_i && j == exit_j) {
        sol[i][j] = 1;
        path.emplace_back(i, j);
        // 输出路径
        for (size_t k = 0; k < path.size(); ++k) {
            cout << " (" << path[k].first << "," << path[k].second << ")";
            if (k != path.size() - 1) cout << ", ";
        }
        cout << endl;
        path.pop_back(); // 回溯移除出口坐标
        sol[i][j] = 0;
        return true;
    }

    // 检查当前位置是否合法
    if (i >= 0 && i < rows && j >=0 && j < cols && maze[i][j] == 1 && sol[i][j] == 0) {
        sol[i][j] = 1;
        path.emplace_back(i, j);

        // 尝试四个方向：下、上、右、左（可根据你的搜索顺序调整）
        if (solveMaze(maze, sol, i+1, j, exit_i, exit_j)) return true;
        if (solveMaze(maze, sol, i-1, j, exit_i, exit_j)) return true;
        if (solveMaze(maze, sol, i, j+1, exit_i, exit_j)) return true;
        if (solveMaze(maze, sol, i, j-1, exit_i, exit_j)) return true;

        // 回溯：当前位置不是路径的一部分
        sol[i][j] = 0;
        path.pop_back();
        return false;
    }
    return false;
}

方法2：从出口反向回溯到入口（适合无法修改求解逻辑的场景） #

如果已经得到了标记好的sol数组，可以从出口坐标出发，反向寻找相邻的、标记为1的坐标（每一步只走一个方向，避免回头），收集路径后反转即可得到正确顺序。

示例代码：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void printPath(int sol[][10], int rows, int cols, int start_i, int start_j, int exit_i, int exit_j) {
    vector<pair<int, int>> reverse_path;
    int curr_i = exit_i;
    int curr_j = exit_j;

    // 从出口走到入口
    while (curr_i != start_i || curr_j != start_j) {
        reverse_path.emplace_back(curr_i, curr_j);
        sol[curr_i][curr_j] = 2; // 标记已访问，防止回头

        // 检查四个方向的相邻坐标
        if (curr_i - 1 >= 0 && sol[curr_i - 1][curr_j] == 1) {
            curr_i--;
        } else if (curr_i + 1 < rows && sol[curr_i + 1][curr_j] == 1) {
            curr_i++;
        } else if (curr_j - 1 >= 0 && sol[curr_i][curr_j - 1] == 1) {
            curr_j--;
        } else if (curr_j + 1 < cols && sol[curr_i][curr_j + 1] == 1) {
            curr_j++;
        }
    }
    reverse_path.emplace_back(start_i, start_j);
    reverse(reverse_path.begin(), reverse_path.end()); // 反转得到入口到出口的顺序

    // 输出路径
    for (size_t k = 0; k < reverse_path.size(); ++k) {
        cout << " (" << reverse_path[k].first << "," << reverse_path[k].second << ")";
        if (k != reverse_path.size() - 1) cout << ", ";
    }
    cout << endl;
}

总结 #

• 方法1是最优解，在搜索过程中直接记录路径，无需额外处理，顺序完全匹配行走轨迹。
• 方法2适合已经生成sol数组的场景，但需要确保路径是唯一的（多路径时需要额外逻辑判断）。

内容的提问来源于stack exchange，提问作者powerpuffgirl