一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
网格中的障碍物和空位置分别用 1
和 0
来表示。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
定义dfs(i, j) 返回从i, j出发到达终点的路径条数。
由于其只能往右和往下,dfs(i, j) = dfs(i + 1, j) + dfs(i, j +1)
递归终止
i ,j为终点时返回1。
实现代码如下:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid.length == 0){
return 0;
}
int M = obstacleGrid.length;
int N = obstacleGrid[0].length;
boolean[][] access = new boolean[M][N];
return dfs(0, 0, obstacleGrid, access);
}
public int dfs(int x, int y, int[][] grid, boolean[][] access){
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || access[x][y] || grid[x][y] == 1){
return 0;
}
if(x == grid.length - 1 && y == grid[0].length - 1){
return 1;
}
access[x][y] = true;
int ans = 0;
ans = dfs(x + 1, y, grid, access) + dfs(x, y + 1, grid, access);
access[x][y] = false;
return ans;
}
}
超时了,很显然这问题得改为dp。
定义dp[i] [j]为从i , j位置出发到达终点的路径数目。
转移方程:
baseline:
上式中M为网络的行数,N为网络的列数,
实现代码如下:
class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
if(grid.length == 0){
return 0;
}
int M = grid.length;
int N = grid[0].length;
if(grid[M - 1][N - 1] == 1){
return 0;
}
int[][] dp = new int[M][N];
dp[M - 1][N - 1] = 1;
for(int i = M - 2; i >= 0; i--){
if(grid[i][N - 1] == 0){
dp[i][N - 1] = 1;
}else{
break;
}
}
for(int j = N - 2; j >= 0; j--){
if(grid[M - 1][j] == 0){
dp[M - 1][j] = 1;
}else{
break;
}
}
for(int i = M - 2; i >= 0; i--){
for(int j = N - 2; j >= 0; j--){
if(grid[i][j] == 1){
continue;
}
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
}
return dp[0][0];
}
}
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
该问题是之前问题的简化版,解法相同,直接给出转移方程和baseline。
转移方程:
baseline:
实现代码如下:
class Solution {
public int uniquePaths(int m, int n) {// C(n + m - 2, n - 1)
int[][] dp = new int[m][n];
for(int i = m - 1; i >= 0; i--){
dp[i][n - 1] = 1;
}
for(int j = n - 1; j >= 0; j--){
dp[m - 1][j] = 1;
}
for(int i = m - 2; i >= 0; i--){
for(int j = n - 2; j >= 0; j--){
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
}
return dp[0][0];
}
}
在二维网格 grid 上,有 4 种类型的方格:
1 表示起始方格。且只有一个起始方格。 2 表示结束方格,且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目,每一个无障碍方格都要通过一次。
示例 1:
输入:[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出:2
解释:我们有以下两条路径:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
示例 2:
输入:[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出:4
解释:我们有以下四条路径:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
示例 3:
输入:[[0,1],[2,0]]
输出:0
解释:
没有一条路能完全穿过每一个空的方格一次。
请注意,起始和结束方格可以位于网格中的任意位置。
提示:
1 <= grid.length * grid[0].length <= 20
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
该问题与之前问题相比不光存在障碍点,方向也变为上下左右四个方向,并且还需要每条路径走过所有的无障碍方格。发现数据范围在20以内,决定使用回溯+dfs求解。
我们使用一整型变量num记录该条路径的走的结点个数,到终点时只需要判断结点个数是否等于所有无障碍方格的个数。为了代码简洁把num初值设为无障碍方格的个数遇到一个减一,最终与0相比即可。
实现代码如下:
class Solution {
private int[][] directs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int uniquePathsIII(int[][] grid) {
boolean[][] access = new boolean[grid.length][grid[0].length];
int startX = 0;
int startY = 0;
// 无障碍方格的数目
int num = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == - 1){
continue;
}
num++;
if(grid[i][j] == 1){
startX = i;
startY = j;
}
}
}
return dfs(startX, startY, grid, access, num);
}
public int dfs(int i, int j, int[][] grid, boolean[][] access, int num){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || access[i][j] || grid[i][j] == -1){
return 0;
}
num--;
if(grid[i][j] == 2){
return num == 0 ? 1 : 0;
}
int ans = 0;
access[i][j] = true;
for(int[] direct : directs){
ans += dfs(i + direct[0], j + direct[1], grid, access, num);
}
access[i][j] = false;
return ans;
}
}