障害物と私の分析グリッドのパスを計算

Question

左上から右下にパスの総数を得ることができるプログラムを作りたいと思います。途中でいくつかの障害があります。

は、例えば、私は、グリッド迷路以下のようにしている場合：それは@から9つのパスが$にある私に教えてください

@ + + + + 
+ + + X X 
+ X + + + 
+ + + X + 
+ X + + X 
+ + + + $ 

（唯一の右または下に移動することができます）。 。したがって、私は最初の障害物なしでグリッドのための小さなプログラムを作った、ここでのコードは次のとおりです。

import java.util.*; 
import java.math.*; 

public class s15 { 
    private static long nChooseK(int k, int n) { 
     BigInteger numerator = p(k,n); 
     BigInteger denominator = p2(k); 
     return numerator.divide(denominator).longValue(); 
    } 

    private static BigInteger p2(int k) { 
     BigInteger r = BigInteger.valueOf(1); 
     while (k != 0) { 
      BigInteger k1 = BigInteger.valueOf(k); 
      r = r.multiply(k1); 

      k--; 
     } 
     return r; 
    } 


    private static BigInteger p(int k, int n) { 
     int p; 
     int s = 1; 
     BigInteger r = BigInteger.valueOf(s); 
     for (int i = 0; i <= k-1; i++) { 
      p = n - i; 
      BigInteger p1 = BigInteger.valueOf(p); 
      r = r.multiply(p1); 
     } 
     return r; 
    } 

    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int x = sc.nextInt(); 
     int y = sc.nextInt(); 

     System.out.println(nChooseK(x, x+y)); 
    } 



} 

、私は最初の5*6迷路は、障害物がなければ、持っているどのように多くのパスを取得するには、このコードを使用してみてください。それから私は462を得るが、私は障害物を考慮しなければならないので、それぞれの障害物から$への道を引いて、21 70 6 15 10 3、驚くべきことに私が462-21-70-6-15-10-3を使用した後、私は9よりもはるかに大きい数を得る私はブロックされていないマイナス合計パス障害に障害なしで合計パスを使用して、それは障害物を持つ合計パスでなければなりません。何が悪かったのか？どうも！

Answer 1

遮断総経路障害を計算することは容易ではないであろう。 @から始まり、下または右に移動し、$で終わり、少なくとも1つの障害物を通過したパスの数でなければなりません。

この問題では、異なるデータスケールを目指す2つのアルゴリズムがあります。

1）Inclusion–exclusion principle

総経路障害物）（=いずれかの障害物を通過する総経路を遮断 - （任意の2つの障害物を通過する合計パス）+（任意の三の障害物を通過する合計パス） - ...

K個の障害物を通過するパスの合計は、列挙型を使用してのみ計算できます。つまり、すべての障害物のサブセットをすべて正確にK個の要素で取り、それらを通過するパスを数えます。

K個の障害物がある場合、（左、下） - （右、上）のペアを形成する2つの障害物がある場合、これらの障害物を通過する経路はありません。 そうでなければ、（左、上）から（右、下）の順に並べ替えることができ、（障害物1から障害物2までの合計パス）* *（障害物Kから$への総経路）。

最後に、aからbまでの合計パスは、nChooseKによって解決できます。どのような長いジャーナル！

Sの障害があると仮定すると、このアルゴリズムの時間複雑さはO（S * 2^S）になります。

2）Dynamic Programming

これは、あなたがすでにDPを知っていたならばはるかに簡単です。もしそうでなければ、私はあなたにGoogleを提案し、最初にそれを学ぶでしょう。要するに

、式

F [i] [j]は、@から始まる総経路を表す障害物を通過しないと（i、j）のセルで終了

f[0][0] = 1 
if cell (i, j) is an obstacle 
    f[i][j] = 0 
else 
    f[0][j] = f[0][j - 1] 
    f[i][0] = f[i - 1][0] 
    f[i][j] = f[i - 1][j] + f[i][j - 1] 
Answer = f[N - 1][M - 1] 

、及び（Nであります、M）はボードの寸法です。

時間複雑度はO（NM）です。

Answer 2

dp[i][j]=dp[i-1][j] + dp[i][j-1]...if g[i-1][j] and g[i][j-1] is free. 
The points neighbor to start point will be of length 1(ofc valid points) 

大丈夫です。下降した人が彼に感謝します。

だからここに私たちが唯一のダウンまたは右に移動することができます

1. を覚えておくべき3つの事があります。だから、私たちは自由であれば2つの点からポイントすることができます。それらは[i-1、j]または[i、j-1]になります。 reacj [i、j]へのパスの数は、[i-1、j]と[i、j-1]（空いている場合）に達する方法の合計に等しくなります。

2. [0、y]または[x、0]のようなエッジケースはほとんど考慮する必要がありません。

ので

dp[i][j]= dp[i-1][j]+dp[i][j-1] if i>=1 & j>=1 
       dp[i][j-1]   if i=0 & j>=1 
       dp[i-1][j]   if i>=1 & j =0 
       1      if i=0 & j =0 
       0      if x[i][j] is obstacle 

回答はdp[row-1][col-1]になります。

Time complexity: O(row*col) 
Space complexity: O(row*col) 

DPアレイは

1 1 1 1 1 
1 2 3 0 0 
1 0 3 3 3 
1 1 4 0 3 
1 0 4 4 0 
1 1 5 9 9