calculate path in a grid with obstacles and my analysis

Question

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!

Answer 1

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).

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)

Okay so the person who downvoted..thanks to him.

So here there is 3 things to remember

1. We can only move in down or right. So we can come to [i,j] point from two points if they are at all free. Those will be [i-1,j] or [i,j-1].

2. The number of paths to reacj [i,j] will be equal to sum of the ways to reach [i-1,j] and [i,j-1] (if free).

3. And we need to consider few edge case like [0,y] or [x,0].

So

   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

Answer will be dp[row-1][col-1].

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

dp array will be

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

Answer 3

For the reference, If you have very few obstacle, Aside from the Inclusion-Exclusion method above, It's possible to sort obstacles by its distance from start so that all obstacle is not contained in any previous obstacle. Now, consider that we can partition every path that passed some obstacle by the first obstacle it passed. We can then calculate for every obstacle, how many path that has this obstacle as first obstacle. Once we know that, Just sum them up and we got the answer.

Time complexity: O(k^2) where k is number of obstacle