7

p x qサイズマトリックスが与えられ、サイズのマトリックスが右 a x b上隅から削除されます。総数を求めます。左上から右下へのパスの数。右と下の動きのみが許可されます。削除されたマトリックスにパスが入ることはありません。

例えば-

 _
|_|_
|_|_|

これは、右上隅から(2x2)マトリックスを削除した後のマトリックスです。(1x1)番号。方法の- 5。

パスの総数はわかりますが、削除した部分に入るパスを削除する方法は非常に基本的で効率的ではありません。

それで、それのためのより良いアルゴリズムはありますか？

4

3 に答える 3

9

グリッドの構造を利用できます。

正方形グリッド上の 1 つのコーナーから別のコーナーへのパスの数は、パスカルの三角形によるグリッドのサイズによって与えられます。(x+y) choose x

各パスは、各対角線上で正確に 1 点を交差する必要があります。

内側の角を通る対角線上のすべての点を取り、それぞれを通る経路の数を計算し、合計します。

O(min(p-a, q-b))これは、一定時間の演算を想定したアルゴリズムにつながります。

あなたの場合: (中心への 2 つのパス) * (中心からの 2 つのパス) + (コーナーを通る 1 つのパス) = (中心を通る 4 つのパス) + (コーナーを通る 1 つのパス) = (5 つのパス)

+-+-+
| | |
+-+-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
于 2012-12-06T13:50:24.217 に答える
6

問題を表すDAG 1でトポロジカル ソートを実行します。

次に、最後 (シンク) から最初 (ソース) まで繰り返します。

f(v) = Sum(f(u)) for each (v,u) in E
base: f(sink) = 1

複雑さはグラフのサイズに比例します (各頂点を正確に 1 回反復します) (行列の次元を使用してO(p*q-a*b))

(1) グラフ G=(V,E) は次のとおりです。

V = { (i,j) | for each i,j in the matrix that was not deleted }
E = { ((i1,j1),(i2,j2)) | (i1,j1) is to the left/up of (i2,j2) }
于 2012-12-06T13:40:12.363 に答える