c++ - 如何使用递归计算从点A到B的可用路径数

我有一个编程任务，要求找到最大尺寸为16的网格上从A点到B点的可用东北路径的数量。

目前，我已经编写了一个程序，该程序能够计算从A点到B点的一条路径，但是不确定如何计算所有可用路径。

目前，我的代码如下所示：

#include <iostream>

using namespace std;
const int max = 17;
const int intial = 16;
int numPath = 0;
int mover(char grid[max][max], int x, int y, int max);

int main()
{
char grid[max][max];

grid[intial][0] = 'A';
int north = 0, east = 0;
cout << "How many points north of A is B? ";
cin >> north;
cout << endl << "How many points east of A is B? ";
cin >> east;
cout << endl;

if (north > 16 && east > 16)
{
    cout << "You entered to high of a number" << endl;
    exit(1);
}
grid[intial - north][east] = 'B';
int paths = mover(grid, north, east, max);

cout << "Number of paths avaliable is " << paths << endl;
}

 int mover(char grid[max][max], int x, int y, int max)
 {


if (grid[x][y] == 'B')
{
    numPath = 1;
}
else
{
    if (x > (intial - x))
    {
        mover(grid, x - 1, y, max);
    }
    if (y > 0)
    {
        mover(grid, x, y + 1, max);
    }
}
return numPath;
}

有人可以帮助将我推向正确的方向吗？

最佳答案

我将概述如何开始：
让我们考虑一个x，y的网格，其中0 路径从0,0（点A）开始，到xmax，ymax（点B）结束。

我们要编写一个递归函数pathCountTo（x，y），以便pathCountTo（xmax，ymax）给出从A到B的路径数。

pathCountTo（0,0）= 1，因为只有一种方法可以从A开始。

共有三种递归情况，您已经确定了两种。
情况1：pathCountTo（0，y）= pathCountTo（0，y-1）。 （到左边缘点的唯一路径是从正下方的点开始。）

情况2：pathCountTo（x，0）= pathCountTo（x-1,0）。 （沿底边的推理相同）。

情况3：pathCountTo（x，y）=？。提示：在最后一种情况下，路径可以从左或从底部开始。