c++ - 计算 n*n 网格中从 (0,0) 到 (n-1,n-1) 的总路径

Question

我正在使用一个简单的回溯算法来查找所有路径，但它没有给出正确的答案。我无法弄清楚错误。我们可以从给定位置上下左右移动。

    Int path(int a[][200],int n,int m,int r,int c) 
    {
        if(n == r - 1 && m == c-1) {
            return 1;
        }
        else if(n >= r || m >= c || n < 0 || m < 0) {
            return 0;
        }
        else if(vis[n][m] == 1) {
            return 0;
        }
        else {
            vis[n][m] = 1;
            int x = path(a,n+1,m,r,c);
            int y = path(a,n,m+1,r,c);
            int u = path(a,n-1,m,r,c);
            int v = path(a,n,m-1,r,c);
            vis[n][m] = 0;
            return (x+y+u+v);
        }
}

Answer 1

找到路径 或计算路径 并不完全相同。我假设您只想计算路径(因为您的问题的标题)，并且您只能向右移动或向下移动。

为此，您实际上并不需要矩阵(表示网格)作为参数。以下是一个简单的(虽然效率不高)递归解决方案，它也适用于 n*m 网格:

int countPaths(int m, int n) {
    if (m == 0 || n == 0)
        return 1;

    return countPaths(m-1, n) + countPaths(m, n-1); 
}

一般n*n格子的数学解是:

(2n 选择 n) = (2*n)!/(n!*n!)

然后，将结果与公式进行比较:

countPaths(1, 1) == 2   // (2*1)!/(1!*1!)=2

countPaths(2, 2) == 6   // (2*2)!/(2!*2!)=6

countPaths(3, 3) == 20  // (2*3)!/(3!*3!)=20

您的回溯方法将给出相同的结果，但有一些注意事项。例如，考虑当 n=2 时，您将需要一个 3x3 矩阵(通常是一个 (n+1)x(n+1) 矩阵)来表示/探索(并标记为 1)2x2 网格的所有路径:

int countPaths(int a[][3],int n, int m, int r, int c) {
        if(n == r-1 && m == c-1) {
            return 1;
        }
        else if(n >= r || m >= c || n < 0 || m < 0) {
            return 0;
        }
        else if(vis[n][m] == 1) {
            return 0;
        }
        else {
            vis[n][m] = 1;
            int x = countPaths(a,n+1,m,r,c);
            int y = countPaths(a,n,m+1,r,c);
            vis[n][m] = 0;
            return (x+y);
        }
} 

然后:

countPaths(vis, 0, 0, 3, 3) == 6  // (2*2)!/(2!*2!)=6