迷宫寻路（Rat in a Maze）回溯算法无输出问题排查求助

你的代码存在两个关键错误，导致无法输出可行路径：

1. isSafe函数参数传递顺序错误 #

isSafe函数定义的参数顺序是：matrix, visited, size, srcx, srcy，但你在findPathUtiltity中调用时，把size和坐标参数的顺序搞反了。比如DOWN方向的调用：

if (isSafe(matrix, visited, srcx + 1, srcy, size))

这里将srcx+1、srcy放在了size前面，和函数定义的参数顺序不匹配，导致边界检查和合法性判断完全错误，程序无法正确识别可走路径。

2. UP方向的逻辑缩进错误 #

你把UP方向的判断代码嵌套在了Right方向的if块内部，这意味着只有当Right方向可行时，才会去检查UP方向。但UP是独立的移动方向，应该和DOWN、LEFT、Right处于同级分支判断中，否则会漏掉大量可能的路径。

修正后的完整代码 #

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

vector<string> ans;

bool isSafe(vector<vector<int>> &matrix, vector<vector<int>> &visited, int size, int srcx, int srcy)
{
    if (srcx >= 0 && srcy >= 0 && srcy < size && srcx < size && matrix[srcx][srcy] == 1 && !visited[srcx][srcy])
    {
        return true;
    }
    else
    {
        return false;
    }
}

void findPathUtiltity(vector<vector<int>> &matrix, vector<vector<int>> &visited, int size, int srcx, int srcy, string temp)
{
    // 到达终点
    if (srcx == size - 1 && srcy == size - 1)
    {
        ans.push_back(temp);
        return;
    }
    visited[srcx][srcy] = 1;
    
    // DOWN
    if (isSafe(matrix, visited, size, srcx + 1, srcy))
    {
        findPathUtiltity(matrix, visited, size, srcx + 1, srcy, temp + "D");
    }
    // LEFT
    if (isSafe(matrix, visited, size, srcx, srcy - 1))
    {
        findPathUtiltity(matrix, visited, size, srcx, srcy - 1, temp + "L");
    }
    // RIGHT
    if (isSafe(matrix, visited, size, srcx, srcy + 1))
    {
        findPathUtiltity(matrix, visited, size, srcx, srcy + 1, temp + "R");
    }
    // UP（修正缩进，成为独立分支）
    if (isSafe(matrix, visited, size, srcx - 1, srcy))
    {
        findPathUtiltity(matrix, visited, size, srcx - 1, srcy, temp + "U");
    }
    
    visited[srcx][srcy] = 0;
    return;
}

vector<string> findPath(vector<vector<int>> &matrix, int size)
{
    ans.clear(); // 每次调用清空结果，避免多次调用时残留旧数据
    if (matrix[0][0] == 0 || matrix[size-1][size-1] == 0)
    {
        return ans;
    }

    vector<vector<int>> visited(size, vector<int>(size, 0));
    findPathUtiltity(matrix, visited, size, 0, 0, "");
    return ans;
}

int main()
{
    vector<vector<int>> matrix = {
        {1, 0, 0, 0, 0},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 1}};
    vector<string> path = findPath(matrix, matrix.size());

    for (const string& p : path)
    {
        cout << p << " ";
    }
    // 输出结果：DDDRRUUURRRDDD DDRRDDD

    return 0;
}

额外优化点说明：

• 在findPath函数开头清空ans，避免多次调用函数时残留之前的结果。
• 增加了终点matrix[size-1][size-1] == 0的判断，如果终点本身不可走，直接返回空结果。

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