Rat In The Maze回溯问题：函数内push_back的vector在main中无输出

问题根因 #

核心问题出在isSafe函数的边界校验逻辑缺失：

• 原isSafe仅判断坐标是否小于迷宫边长n，未校验i >= 0、j >= 0的合法性
• 递归尝试向上（U）、向左（L）移动时，会出现负坐标，直接访问二维数组触发越界崩溃，程序提前终止，没有机会将合法路径存入ans输出

修复方案 #

修改isSafe函数，补充坐标非负校验即可，修改后的isSafe代码如下：

bool isSafe(vector<vector<int>> &m, int i, int j, int n)
{
    // 补充i、j非负判断，避免越界访问
    if (i >= 0 && j >= 0 && i < n && j < n && m[i][j] == 1)
        return true;
    return false;
}

可选优化 #

可以在终点判断条件中补充终点可通行校验，避免终点为0时存入无效路径：

if (i == n - 1 && j == n - 1 && m[i][j] == 1)
{ 
    ans.push_back(out);
    return 0;
}

修复后完整验证代码 #

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

bool isSafe(vector<vector<int>> &m, int i, int j, int n)
{
    if (i >= 0 && j >= 0 && i < n && j < n && m[i][j] == 1)
        return true;
    return false;
}

int RIM(vector<vector<int>> &m, int i, int j, int n, string out, vector<string> &ans)
{
    if (i == n - 1 && j == n - 1 && m[i][j] == 1)
    { 
        ans.push_back(out);
        return 0;
    }
    if (isSafe(m, i, j, n))
    {
        m[i][j] = 2;
        out.push_back('D');
        RIM(m, i + 1, j, n, out, ans);
        out.pop_back();
        out.push_back('R');
        RIM(m, i, j + 1, n, out, ans);
        out.pop_back();
        out.push_back('U');
        RIM(m, i - 1, j, n, out, ans);
        out.pop_back();
        out.push_back('L');
        RIM(m, i, j - 1, n, out, ans);
        out.pop_back();
        m[i][j] = 1;
        return 0;
    }
    return 0;
}

int main()
{
    vector<string> ans;
    vector<vector<int>> m{
        {1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
    RIM(m, 0, 0, m.size(), "", ans);
    for (auto i : ans)
        cout << i << " ";
    return 0;
}

修改后运行给定测试用例，即可输出预期结果DDRDRR DRDDRR。

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