类似 https://leetcode.com/problems/unique-paths-ii/
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
我用了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;
}