algorithm - 没有办法在网格中走 M 步

Question

您位于坐标 x,y 的网格中。行的尺寸为 dx,dy。一步中，您可以在行或列中向前或向后走一步。你有多少种方法可以走 M 步，这样你就不会在任何时候离开网格？
你可以多次访问同一个位置。
如果您对任何 x,y 要么 x,y <= 0 要么 x,y > dx,dy，您离开网格。
1 <= 米 <= 300
1 <= x,y <= dx,dy <= 100

输入:
男
××
dx dy

输出:
没有办法

例子:
输入:
1
6 6
12 12

输出:
4

例子:
输入:
2
6 6
12 12

输出:
16
如果你在位置 6,6 那么你可以走到 (6,5),(6,7),(5,6),(7,6)。

我卡在如何使用帕斯卡三角来解决它。这是正确的方法吗？我已经尝试过蛮力，但它太慢了。

C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

T[startpos][stp]
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]

Answer 1

您可以使用您提供的公式解决 1d 问题。

设 H[pos][step] 是使用给定步数水平移动的方法数。
V[pos][step] 是垂直移动给定步数的方法数。

您可以迭代将水平设置的步数 i = 0..M
所以移动的方式数是 H[x][i]*V[y][M-i]*C[M][i]，其中 C 是二项式系数。

您可以在 O(max(dx,dy)*M) 中构建 H 和 V，并在 O(M) 中执行第二步。

编辑: 关于 H 和 V 的说明。 假设您有一条直线，其中有 d 个单元格:1,2,...,d。你站在单元格 pos 然后 T[pos][step] = T[pos-1][step-1] + T[pos+1][step-1]，因为你可以向前或向后移动。

基本情况是 T[0][step] = 0，T[d+1][step] = 0，T[pos][ 0] = 1。

我们假设 d = dx 构建 H，假设 d = dy 构建 V。

编辑 2: 基本上，算法的思想是因为我们在两个维度之一移动并且检查也独立地基于每个维度，我们可以拆分 2d 问题在 2 个 1d 问题中。