I want to make a program which could get the total number of paths from left top to right down spot, and there will be a few obstacles in the way.
For example if I have a grid maze like below:
@ + + + +
+ + + X X
+ X + + +
+ + + X +
+ X + + X
+ + + + $
it should tell me there are 9 paths from @ to $ (only can move right or down). Therefore I first made a little program for grid without any obstacles, here is the code:
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));
}
}
then I first try to use this code to get how many paths 5*6 maze has if without any obstacles. Then I get 462, but I have to consider obstacles so I minus 462 with paths from each obstacles to $, and I get numbers : 21 70 6 15 10 3, surprisingly after I use 462-21-70-6-15-10-3, I get a number which is much bigger than 9, I think if I use the total paths without obstacles to minus total path obstacles blocked, it should be the total path with obstacles. What went wrong? Thx!
The total path obstacles blocked is not that easy to calculate. It should be the number of paths that starts from @, moves down or right, ends at $, and passed at least one obstacle.
For this problem, there are two algorithms which aim to different data scales.
1) Inclusion–exclusion principle
The total paths obstacle blocked = (The total paths that pass any one obstacle) - (The total paths that pass any two obstacles) + (The total paths that pass any three obstacles) - ...
The total paths that pass any K obstacles can only be calculated using enumeration. That is, take all subsets of the whole obstacles with exactly K elements and count the paths that pass them.
Given K obstacles, if there are any two obstacles forms a (left, down) -- (right, top) pair, there would be no paths that pass these obstacles. Otherwise, we can sort them from (left, top) to (right, down) and the count would be (the total path from @ to obstacle 1) * (the total path from obstacle 1 to obstacle 2) * ... * (the total path from obstacle K to $).
Finally, the total path from a to b can be solved by nChooseK. What a long journal!
Assuming there are S obstacles at all, the time complexity of this algorithm would be O(S*2^S).
This is much easier if you've already known DP. If not, I would suggest you google and learn it first.
In short, the formula is
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]
where f[i][j] represents the total paths that starts from @, passes no obstacle and ends at cell (i, j), and (N, M) is the dimension of the board.
The time complexity is O(NM).