dfs迷宫问题的细节

Question

#include <iostream>
using namespace std;
int arr[100][100]; //arr为地图数组（1为空地，2为障碍物）
int vis[100][100]; //vis为访问数组（1为已访问，0为未访问）
int dx[4] = {0,1,0,-1};  //方向数组：x方向
int dy[4] = {1,0,-1,0};  //方向数组：y方向
int MIN = 99999999;         //最小步数，初始化为较大的数a
int p, q;          //终点坐标
int n, m;           //n,m为数组的长度
int step = 0;
int tx, ty;
void dfs(int x, int y, int step)
{
    if (x == p && y == q)     //reach to the end
    {
        if (step < MIN)    //判断是否步数较小，较小的赋值为MIN
        {
            MIN = step;
            return;
        }
    }
    //not reach to the end
    for (int k = 0; k <= 3; k++)   //右下左上，顺时针试探
    {
         tx = x + dx[k];      //加上x方向数组的第一个值
        ty = y + dy[k];        //加上y方向数组的第一个值
        if (arr[tx][ty] == 1 && vis[tx][ty] == 0) //空地且未访问
        {
            vis[tx][ty] = 1;      //设置为已访问
            dfs(tx, ty, step + 1);  //递归继续探索
            vis[tx][ty] = 0;     //设置为未访问
        }
        
    }
}



int main()
{
    int startx, starty;  //startx为起点的行坐标, starty为列坐标
    cout << "输入数组的长度:";
    cin >> n >> m;
    cout << "初始化数组:(1为空地，2为障碍物)";
    for (int i = 1; i <= n; i++)       //下标从1开始
    {
        for (int j = 1; j <= m; j++)  
        {
            cin >> arr[i][j];
        }
    }
    cout << "输入起点坐标和终点坐标:";
    cin >> startx >> starty >> p >> q;
    vis[startx][starty] = 1;    //！注意起点访问时也要设置为已访问
    dfs(startx,starty,step);
    cout << MIN;
    return 0;
}

dfs迷宫问题：为什么int tx, ty;这句话写在循环里面就正确：用一个全局变量来定义就答案错误；
测试用例：
5 5
1 1 1 1 1
1 2 1 1 1
1 1 2 1 2
1 2 1 1 1
1 1 1 2 1

正确答案应该是6
但是：int tx, ty;这句话写在循环里面答案就是6：用一个全局变量来定义就答案就是8

Answer 1

该回答引用自GPT-3.5,由博主GIS_Liu编写：

问题的关键在于循环中对 tx 和 ty 的定义位置。如果将 int tx, ty; 定义在循环外，那么在每次递归调用 dfs 函数时，tx 和 ty 的值会被保留，因此在下一次循环中，它们的值可能已经被修改，导致错误的结果。

而将 int tx, ty; 定义在循环内部，则每次循环都会重新定义 tx 和 ty，确保在每次递归调用 dfs 函数时，它们都是新的变量，不会受到之前递归调用的影响，从而保证了结果的正确性。

因此，为了正确计算路径长度，应该将 int tx, ty; 定义在循环内部，以确保在每次递归调用时都是新的变量。

如果该回答解决了您的问题，请采纳！如果没有，请详述问题所在！