如何用深度搜索出需要的那条路？c++

Question

n m t
3 4 7
S.X.
..X.
...D
n等于行，m等于列，t为步数，S为起始位置，要在刚好t步到达D。

 #include <iostream>
#include <cstring>
using namespace std;
int n,m,t,sum,flag=0;
int x2,y2;
char a[10][10];
int b[10][10];
int xy[][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int i,int j)
{
    int tx,ty,k;
    b[i][j]=1;
    for (k=0;k<4;++k)
    {
        tx=i+xy[k][0] ;
        ty=j+xy[k][1] ;
        if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]!='X'&&b[tx][ty]==0)
        {
            sum++;
            if (sum==t&&x2==tx&&y2==ty)//找到所用步数相等且刚好在‘D’点那里
            {
                flag=1;
                return;
            }
            dfs(tx,ty);
            b[tx][ty]=0 ;//不符合就回溯（不知道有没有用错）
            sum--;
        }
    }
}
int main()
{
    int i,j,x1,y1;
    while(cin >> n >> m >> t)
    {
        sum=0;
        flag=0;
        memset(b,0,sizeof(b));
        for(i=0;i<n;++i)
        {
            cin >> a[i] ;
        }
        for(i=0;i<n;++i)
        {
            for (j=0;j<m;++j)
            {
                if (a[i][j]=='S')
                {
                    x1=i;
                    y1=j;
                }
                else if (a[i][j]=='D')
                {
                    x2=i;
                    y2=j;
                }
            }
        }
        dfs(x1,y1);
        cout << "sum: " << sum << " flag: " << flag << endl;  
        for(i=0;i<n;++i)//看一下标记的路径
        {
            for(j=0;j<m;++j)
            {
                cout << b[i][j] << " " ;
            }
            cout << endl;
        }
        if (flag==1&&sum==t)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

怎样才能实现啊？

Answer 1

该回答引用ChatGPT-3.5，仅供参考，不保证完全正确

您的代码已经实现了使用深度优先搜索（DFS）来查找从起始位置到达目标位置的路径，且步数刚好为t的情况。以下是对您代码的一些改进和解释：

1. 没有必要使用全局变量flag来标记是否找到路径。可以将函数dfs的返回类型改为bool，并在找到目标位置时返回true，否则返回false。

2. 函数dfs中的回溯操作是正确的，将b[tx][ty]重置为0可以正确回溯。

3. 可以简化一些变量的声明和初始化。例如，将x1、y1、x2、y2的声明移至对应的位置，无需在代码开头声明。

4. 可以考虑添加一些边界条件的判断，以提高代码的鲁棒性。例如，在递归调用dfs之前，可以先判断sum是否已经达到了t的值，如果达到则直接返回。

下面是对代码进行了改进的版本：

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

int n, m, t;
int x2, y2;
char a[10][10];
int b[10][10];
int xy[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool dfs(int i, int j, int sum) {
    if (sum == t && i == x2 && j == y2) {
        return true;  // 找到目标位置
    }

    b[i][j] = 1;

    for (int k = 0; k < 4; ++k) {
        int tx = i + xy[k][0];
        int ty = j + xy[k][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && a[tx][ty] != 'X' && b[tx][ty] == 0) {
            if (dfs(tx, ty, sum + 1)) {
                return true;  // 在下一步找到目标位置
            }
            b[tx][ty] = 0;  // 回溯
        }
    }

    return false;  // 未找到目标位置
}

int main() {
    int x1, y1;
    while (cin >> n >> m >> t) {
        memset(b, 0, sizeof(b));

        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] == 'S') {
                    x1 = i;
                    y1 = j;
                } else if (a[i][j] == 'D') {
                    x2 = i;
                    y2 = j;
                }
            }
        }

        bool found = dfs(x1, y1, 0);

        cout << "sum: " << t << " found: " << found << endl;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout

 << b[i][j] << " ";
            }
            cout << endl;
        }

        if (found) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

希望这可以帮助到您！如果您还有其他问题，请随时提问。