algorithm - 矩阵中的路径数

Question

给定一个 p x q 大小的矩阵，从右上角移除一个大小为 a x b 的矩阵。找到总数。从左上角到右下角的路径，只允许向右和向下移动。任何路径都不应进入删除的矩阵。

例如-

 _
|_|_
|_|_|

这是从右上角移除 (1x1) 矩阵后的 (2x2) 矩阵。不。方式 - 5。

我能够找出路径的总数，但我正在考虑的消除进入删除部分的路径的方法非常初级，因此效率不高。

那么，有没有更好的算法呢？

Answer 1

您可以利用网格的结构:

正方形网格上从一个角到另一个角的路径数由帕斯卡三角形的网格大小给出:(x+y) choose x

每条路径必须恰好穿过每条对角线上的一个点。

取通过内角的对角线上的所有点，计算通过每个点的路径数，然后求和。

这导致O(min(p-a, q-b)) 算法假定常数时间算术。

在你的例子中:(到中心的两条路径)*(从中心开始的两条路径)+(通过拐角的一条路径)=(通过中心的四条路径)+(通过拐角的一条路径)=(五条路径)

+-+-+
| | |
+-+-A-+-+
| | | | |
+-B-+-+-+
| | | | |
C-+-+-+-+
| | | | |
+-+-+-+-+

  (1+2) choose 1 * (2+3) choose 2 (through A)
+ (2+1) choose 2 * (3+2) choose 3 (through B)
+ (3+0) choose 3 * (4+1) choose 4 (through C)

= 3 choose 1 * 5 choose 2
+ 3 choose 2 * 5 choose 3
+ 3 choose 3 * 5 choose 4

= 3*10
+ 3*10
+ 1*5

= 30+30+5 = 65 paths