This quesiton is similar to https://leetcode.com/problems/unique-paths-ii/
Only change here is, we can go
- down
- up
- right
- left
Example:
Input :
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
Output : 2
Input :
{0, 0, 0},
{0, 1, 0},
{0, 0, 0},
{0, 0, 0}
Output: 7
My Attempt so far is using backtracking
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
return 0;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
final int sx = 0, sy = 0;
final int dx = m - 1, dy = n - 1;
return uniquePaths(obstacleGrid, m, n, sx, sy, dx, dy);
}
private int uniquePaths(int[][] maze, int m, int n, int sx, int sy, int dx, int dy) {
//1. Our goal: To reach destination cell (m-1,n-1), once reach it counted as one path
if (sx == dx && sy == dy)
return 1;
int path = 0;
if (isSafe(sx, sy, m, n, maze)) {
maze[sx][sy] = -1; //not available for next round
path = uniquePaths(maze, m, n, sx + 1, sy, dx, dy) //down
+ uniquePaths(maze, m, n, sx, sy + 1, dx, dy)//right
+ uniquePaths(maze, m, n, sx - 1, sy, dx, dy) //Up
+ uniquePaths(maze, m, n, sx, sy - 1, dx, dy);//Left
maze[sx][sy] = 0; // available for next round
}
return path;
}
private boolean isSafe(int sx, int sy, int m, int n, int[][] maze) {
if (sx >= m || sy >= n || sx < 0 || sy < 0 || maze[sx][sy] == -1 || maze[sx][sy] == 1) //Line change from UniqPathsI
return false;
return true;
}
But when apply same logic as i applied in https://leetcode.com/problems/unique-paths-ii/ to cache already pre-computed result and do the same, i get wrong result
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
return 0;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int dp[][] = new int[m][n];
for (int i = 0; i < m; i++)
Arrays.fill(dp[i], -1);
final int sx = 0, sy = 0;
final int dx = m - 1, dy = n - 1;
return uniquePaths(obstacleGrid, dp, m, n, sx, sy, dx, dy);
}
private int uniquePaths(int[][] maze, int dp[][], int m, int n, int sx, int sy, int dx, int dy) {
int count = 0;
if (isSafe(sx, sy, m, n, maze)) {
if (sx == dx && sy == dy)
return dp[sx][sy] = 1;
if (dp[sx][sy] != -1)
return dp[sx][sy];
maze[sx][sy] = -1;
count = uniquePaths(maze, dp, m, n, sx + 1, sy, dx, dy) //down
+
uniquePaths(maze, dp, m, n, sx - 1, sy, dx, dy) //up
+
uniquePaths(maze, dp, m, n, sx, sy + 1, dx, dy) // right
+
uniquePaths(maze, dp, m, n, sx, sy - 1, dx, dy); //left
maze[sx][sy] = 0;
return dp[sx][sy] = count;
}
return count;
}
private boolean isSafe(int sx, int sy, int m, int n, int[][] maze) {
if (sx >= m || sy >= n || sx < 0 || sy < 0 || maze[sx][sy] == 1 || maze[sx][sy] == -1)
return false;
return true;
}What i understood, why its not working because of early return, it may be possible as of the state, all possibilities of sx,sy has not been computed.
if (dp[sx][sy] != -1)
return dp[sx][sy];but it returns.
How do we solve this problem using dp, it seems to me a dp but its not working either way 'top-down' or 'bottom-up'
Comments (3)