# Unique Paths III

​A robot is located at the top-left corner of a m x n grid (marked as ‘Start’ in the diagram below). The robot can either move right or diagonally at any point of time. The robot is trying to reach the top-right corner of the grid (marked as ‘Star’ in the diagram below). How many possible unique paths are there?

Followings are the moves allowed at any given point of time:

```Consider i is the row index and j is the column index for the 2D grid.
Allowed Moves:
1. i, (j + 1) -> Right
2. (i + 1), (j + 1) -> Diagonnaly Down
3. (i - 1), (j + 1) -> Diagonnaly Up```

This is an Extension of Find Unique Paths in a 2D Grid from Source to Destination. Only the allowed moves are different from source to destination. The problem can also be solved using backtracking and Memoization.

```class PathFinder {

int height, width;

public int countPaths(int h, int w) {
this.height = h;
this.width = w;
int[][] board = new int[h][w];
board[w - 1] = 1;
int count = backTrack(board, 0, 0);
return count;
}

private int backTrack(int[][] board, int i, int j) {
if (i >= height || j >= width || i < 0) return 0;
if (board[i][j] != 0) return board[i][j];
int c1 = backTrack(board, i, (j + 1));
int c2 = backTrack(board, (i + 1), (j + 1));
int c3 = backTrack(board, (i - 1), (j + 1));
board[i][j] = (c1 + c2 + c3);
return board[i][j];
}
}

public class UniquePath_III {
public static void main(String[] args) {
PathFinder pathFinder = new PathFinder();
int path = pathFinder.countPaths(3, 3);
System.out.println(path);
}
}
```

Complexity Analysis

• Time Complexity: `O(mn)`. Each `cell` will be calculated once and only once.
• Space Complexity : `O(mn)`. Size of the 2D board used as a cache for backtracking.

Categories: Backtracking, DFS