Q:

calculate path in a grid with obstacles and my analysis

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!

A:

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).
2) Dynamic Programming
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).

