题解 | #迷宫问题#

C++版本的DFS解法，一些细节：

• 常用的变量可以设成全局变量，这样可以避免DFS函数需要传入的参数太多；
• 每走一步把当前位置设为1，然后遍历上下左右位置，选择不为1的进行尝试，每尝试一次之后都要恢复之前的状态，避免整体刷新地图。

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

struct Cord
{
    int x, y;
};

int v[10][10];
vector<Cord> p, ans; // p 是当前的路径，ans 保存当前的最短路径
int R, C;
vector<Cord> dir = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

void dfs(int x, int y)
{
    if (x == R - 1 && y == C - 1) // 到达出口，尝试更新最短路径
    {
        if (ans.empty() || p.size() < ans.size())
            ans.assign(p.begin(), p.end());
        return;
    }
    for (auto d : dir)
    {
        int nx = d.x + x;
        int ny = d.y + y;
        if (x >= 0 && x < R && y >= 0 && y < C && !v[nx][ny])
        {
            v[nx][ny] = 1;
            p.push_back({ nx, ny });
            dfs(nx, ny);
            // 恢复
            v[nx][ny] = 0;
            p.pop_back();
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            cin >> v[i][j];
    p.push_back({ 0, 0 });
    dfs(0, 0);
    for (auto cord : ans)
        printf("(%d,%d)\n", cord.x, cord.y);
}
// 64 位输出请用 printf("%lld")