使用深度优先搜索所有可能路径

Question

对于给定的连通图，起点和终点，如果使用使用深搜的方法解题，如何判断一共有多少可能的路径。
以下面的问题为例：
给定一个n*m的矩阵，其左上角坐标为(0,0)右下角坐标为(n-1,m-1)，假设从左上角开始，每次可以向右走一格或者向下走一格，要走到右下角，请问一共有多少种可能的路径？

#include <iostream>  
#include <algorithm>  
using namespace std;
bool maxt[100][100] = { false };
int end1, end2;
int path = 0;
void dfs(int i,int j) {
    maxt[i][j] = true;
    if (i == end1 && j == end2) {
        path++; return;//请问找到路径后正确的处理操作是什么？
    }
    if (!maxt[i + 1][j] && i + 1 <=end1) { dfs(i + 1, j); }
    if (!maxt[i][j + 1] && j + 1 <=end2) { dfs(i, j + 1); }
}
int main() {
    int n, m; cin >> n >> m;
    end1 = n - 1; end2 = m - 1;
    dfs(0, 0);
    cout << path << endl;
    return 0;
}

求正确的dfs代码应该怎么写？

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
using namespace std;

int maxt[100][100] = { false };
int end1, end2;
int path = 0;

void dfs(int i, int j) {
    maxt[i][j] = true;
    if (i == end1 && j == end2) {
        path++;
    } else {
        if (i + 1 <= end1 && !maxt[i + 1][j]) {
            dfs(i + 1, j);
        }
        if (j + 1 <= end2 && !maxt[i][j + 1]) {
            dfs(i, j + 1);
        }
    }
    maxt[i][j] = false; // 回溯，撤销当前节点的访问状态
}

int main() {
    int n, m;
    cin >> n >> m;
    end1 = n - 1;
    end2 = m - 1;
    dfs(0, 0);
    cout << path << endl;
    return 0;
}

在这个代码中，我们使用深度优先搜索（DFS）遍历所有可能的路径。当我们到达终点时，我们将path加1。在访问下一个节点之前，我们需要检查该节点是否已经被访问过，如果没有被访问过，我们可以继续访问。在访问完一个节点的所有邻居后，我们需要将其访问状态撤销，以便在后续的搜索过程中可以重新访问该节点。这是通过在dfs函数的最后将maxt[i][j]设置为false来实现的。