Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?

FOLLOW UP

Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

**My initial thoughts:**

- Base case: f(N, 0) = 1, f(0, N) = 1
- Recursion: f(N, N) = f(N, N-1) + f(N-1, N)

**My initial codes (solution):**

public static int allPossiblePaths(int M, int N) {
if (N == 0 || M == 0)
return 1;
return allPossiblePaths(M - 1, N) + allPossiblePaths(M, N - 1);
}
public static int AllPossiblePathsWithObstacles(int M, int N,
Set<Pair<Integer>> obstacles) {
if (obstacles.contains(new Pair<Integer>(M, N)))
return 0;
else {
if (N == 0 || M == 0)
return 1;
return AllPossiblePathsWithObstacles(M - 1, N, obstacles)
+ AllPossiblePathsWithObstacles(M, N - 1, obstacles);
}
}

If we would also like to print out all paths:

public static void PrintAllPossiblePathsWithObstacles(int M, int N,
Set<Pair<Integer>> obstacles, String path) {
if (obstacles.contains(new Pair<Integer>(M, N)))
return;
else {
if (M == 0) {
for (int i = 0; i < N; ++i)
path = "DOWN " + path;
System.out.println(path);
} else if (N == 0) {
for (int i = 0; i < M; ++i)
path = "RIGHT " + path;
System.out.println(path);
} else {
PrintAllPossiblePathsWithObstacles(M - 1, N,
obstacles, "RIGHT " + path);
PrintAllPossiblePathsWithObstacles(M, N - 1,
obstacles, "DOWN " + path);
}
}
}

### Like this:

Like Loading...

*Related*

Murali

Jul 08, 2012@ 14:10:59One more way to look at it,

Let us call the down move as “1” and right move as a “0” then the path should be a string containing n “1”s and n “0”s (something like this 11111111…00000…).

The total number of permutations(without repetition) of this string is the answer. That will be (2n!) / (n! * n!).

Print all the permutations of this string to find all possible paths

Runhe Tian

Jul 08, 2012@ 14:12:27Thanks!

Ashu

Sep 18, 2012@ 01:02:10This code is not printing correct paths for the following Grid, where 1 is a obstacle

0,1,0

0,1,0

0,0,0

Ashu

Sep 18, 2012@ 01:05:40Below is the corrected code of Java, for above case as well

ArrayList allPaths = new ArrayList();

public void PrintAllPossiblePathsWithObstacles(int M, int N,

int[][] obstacles, String path) {

if (obstacles[M][N] == 1)

return;

else {

if (M == 0) {

for (int i = 0; i < N; ++i)

{

if(obstacles[M][i] == 1)

return;

path = "RIGHT " + path;

}

System.out.println(path);

allPaths.add(path);

} else if (N == 0) {

for (int i = 0; i < M; ++i)

{

if(obstacles[i][N] == 1)

return;

path = "DOWN " + path;

}

System.out.println(path);

allPaths.add(path);

} else {

PrintAllPossiblePathsWithObstacles(M – 1, N, obstacles, "DOWN " + path);

PrintAllPossiblePathsWithObstacles(M, N – 1, obstacles, "RIGHT " + path);

}

}

}

Ashu

Sep 18, 2012@ 01:11:33I think I came up with this finally short and crisp version of the code that works for all the cases

ArrayList allPaths = new ArrayList();

public void PrintAllPossiblePathsWithObstacles(int M, int N,

int[][] obstacles, String path) {

if (obstacles[M][N] == 1)

return;

else if(M == 0 && N == 0)

System.out.println(path);

else {

if(M – 1>=0 )

PrintAllPossiblePathsWithObstacles(M – 1, N, obstacles, “DOWN ” + path);

if(N -1 >=0 )

PrintAllPossiblePathsWithObstacles(M, N – 1, obstacles, “RIGHT ” + path);

}

}