没有办法行走中号的步骤在一个网格 [英] No of ways to walk M steps in a grid

问题描述

您是坐落在一个网格，在X，Y位置。行的尺寸是DX，DY。在一个步骤中，您可以行或列前前后后走一步。有多少种方法你能，采取并购等步骤，你不要离开电网在任何时候？
可以访问相同的位置不止一次。
离开网格如果为任何的x，y任一的x，y＆所述; = 0或X，Y> DX，DY
。 1＆LT; = M＆LT; = 300
1其中; = X中，Y = DX，DY＆其中; = 100

输入：
中号
X Y
DX DY

输出：
没有办法

例：
输入：
1
6 6
12 12

输出：
4

例：
输入：
2
6 6
12 12

输出：
16
如果你所在的位置6,6，那么你可以步行到（6,5），（6,7），（5,6），（7,6）。

我停留在如何使用杨辉三角解决it.Is，正确的方法？我已经尝试蛮力，但其速度太慢。

  C [I] [J]，帕斯卡三角
C [I] [J] = C [我 -  1] [J  -  1] + C [我 -  1] [J]。

T [startpos] [STP]
T [POS] [STP] = T [POS + 1] [STP  -  1] + T [POS  -  1] [STP  -  1]
 

解决方案

将是一个O的一种方式（N ^ 3）动态规划的解决方案：

prepare一个三维数组：

  INT Z [DX] [颐] [M]
 

当Z [i] [j]的[n]的持有，从位置（i，j）和最后N开始移动路径的数量。

基本情况为Z [Ⅰ] [j]的[0] = 1对于所有的i，J

递归情况下为Z [Ⅰ] [j]的[N + 1] = Z [I-1] [j]的[n]的+ Z [I + 1] [j]的[n]的+ Z [I] [J-1] [n]的+ Z [I] [J + 1] [n]的（只包括在属于地图上的Sumation公司计）

在数组中充满了回报Z [X] [Y] [M]

为了节省空间，你可以放弃每一个二维数组对n用完后。

You are situated in an grid at position x,y. The dimensions of the row is dx,dy. In one step, you can walk one step ahead or behind in the row or the column. In how many ways can you take M steps such that you do not leave the grid at any point ?
You can visit the same position more than once.
You leave the grid if you for any x,y either x,y <= 0 or x,y > dx,dy.
1 <= M <= 300
1 <= x,y <= dx,dy <= 100

Input:
M
x y
dx dy

Output:
no of ways

Example:
Input:
1
6 6
12 12

Output:
4

Example:
Input:
2
6 6
12 12

Output:
16
If you are at position 6,6 then you can walk to (6,5),(6,7),(5,6),(7,6).

I am stuck at how to use Pascal's Triangle to solve it.Is that the correct approach? I have already tried brute force but its too slow.

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]

解决方案

One way would be an O(n^3) dynamic programming solution:

Prepare a 3D array:

int Z[dx][dy][M]

Where Z[i][j][n] holds the number of paths that start from position (i,j) and last n moves.

The base case is Z[i][j][0] = 1 for all i, j

The recursive case is 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] (only include terms in the sumation that are on the map)

Once the array is filled out return Z[x][y][M]

To save space you can discard each 2D array for n after it is used.

这篇关于没有办法行走中号的步骤在一个网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！