没有办法在网格中走M步

Question

您位于x,y位置的网格中.行的尺寸为dx,dy.只需一步,您就可以在行或列中前进或后退一步.你有多少种方法可以采取M步,这样你就不会在任何时候离开网格？
您可以多次访问同一位置.
如果您对x,y x,y <= 0或x,y> dx,dy,则离开网格.
1 <= M <= 300
1 <= x,y <= dx,dy <= 100

输入:
M
xy
dx dy

输出:
没有方法

示例:
输入:
1
6 6
12 12

产量:
4

示例:
输入:
2
6 6
12 12

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

我坚持如何使用Pascal的三角形来解决它.这是正确的方法吗？我已经尝试过蛮力,但速度太慢了.

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

一种方法是 O(n^3) 动态规划解决方案：

准备一个 3D 数组：

int Z[dx][dy][M]

其中 Z[i][j][n] 保存从位置 (i,j) 开始且最后 n 个移动的路径数。

对于所有 i、j，基本情况是 Z[i][j][0] = 1

递归情况是 Z[i][j][n+1] = Z[i-1][j][n] + Z[i+1][j][n] + Z[i][j- 1][n] + Z[i][j+1][n]（仅包括地图上的总和项）

数组填满后返回 Z[x][y][M]

为了节省空间，您可以在使用 n 后丢弃每个 2D 数组。