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

Question

我有一个编程作业要求在最大尺寸为 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;
}

有人可以帮助我朝着正确的方向前进吗？

Answer 1

我将概述我将如何开始: 让我们考虑一个 x,y 的网格，其中 0 <= x <= xmax 和 0 <= y <= ymax。 路径从 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) = ?。提示:在最后一种情况下，路径可以从左侧或底部开始。