给定一个N X N
大小的网格。它的左下点是(0,0)
,右上元素是(N-1,N-1)
。
我们可以在顶部或右侧横穿网格。我们必须找到从左下到右上的遍历方法在每一条路上都有一些检查站我们必须参观至少有一个有效路径。
示例:让N=5
在(2,2)
有一个检查点,那么这里的答案是36
。
注意:我只需要计算有效的路径,而不必担心找到它们。
有什么方法可以有效地计算它们?
最佳答案
你必须知道两件事:
Rule of product:表示从起点到终点的路数等于从起点到中点的路数*从中点到终点的路数。
c(r,r+u)(如果你想从R
移动到U
,那么(a,b)
和(c,d)
,以及R = c-a
)是一个网格中从左下到右上有多少种方式的答案。
在我的第二条规则的例子中,我们有:
从U = d-b
移动到C(R,R+U) = (R+U)!/R!U!
的次数,因为从(0,0)
向右移动两次后,您到达(2,2)
,从0
向上移动两次后,您到达2
so0
和2
soR=2
对于U=2
和C(2,2+2) = C(2,4) = 4!/2!2! = 6
从R
移动到U
的次数也是(2,2)
根据第一条规则,我们有所有可能移动的次数:(4,4)
关于c++ - 计算具有多个检查点的网格中的路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28432169/