## All possible paths for a robot moving along a NxN grid

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?
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);
}
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5bcfc71780a64', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5bcfc71780a8c',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5bcfc71780a8e',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. One 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

• Thanks!

2. This code is not printing correct paths for the following Grid, where 1 is a obstacle
0,1,0
0,1,0
0,0,0

• Below 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);
} else if (N == 0) {
for (int i = 0; i < M; ++i)
{
if(obstacles[i][N] == 1)
return;

path = "DOWN " + path;
}
System.out.println(path);
} else {
PrintAllPossiblePathsWithObstacles(M – 1, N, obstacles, "DOWN " + path);
PrintAllPossiblePathsWithObstacles(M, N – 1, obstacles, "RIGHT " + path);
}
}
}

3. I 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);
}
}