首页 > 试题广场 >

求路径 ii

[编程题]求路径 ii

热度指数：15943 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个m*n的地图，其中加入了一些障碍。每次只能向下或者向右走，问从左上角走到右下角有多少不同的路径？

分别用0和1代表空区域和障碍

例如

下图表示有一个障碍在3*3的图中央。

[
    [0,0,0],
    [0,1,0],
    [0,0,0]
]

有2条不同的路径

备注：m和n不超过100.

示例1

输入

[[0,1]]

输出

示例2

输入

[[1],[1]]

输出

算法知识视频讲解

Java

日常不想上班的码农

import java.util.*;


public class Solution {
    /**
     * 
     * @param obstacleGrid int整型二维数组 
     * @return int整型
     */
    public int uniquePathsWithObstacles (int[][] obstacleGrid) {
        // write code here
        int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;
		if (m == 1) {
			for (int i = 0; i < n; i++) {
				if (obstacleGrid[0][i] == 1) {
					return 0;
				}
			}
			return 1;
		}
		if (n == 1) {
			for (int i = 0; i < m; i++) {
				if (obstacleGrid[i][0] == 1) {
					return 0;
				}
			}
			return 1;
		}
		int[][] dp = new int[m][n];
		boolean flag = false;
		for (int i = 0; i < m; i++) {
			if (obstacleGrid[i][0] == 0 && !flag) {
				dp[i][0] = 1;
			}
			else if (obstacleGrid[i][0] == 1) {
				flag = true;
			}
		}
		flag = false;
		for (int j = 0; j < n; j++) {
			if (obstacleGrid[0][j] == 0 && !flag) {
				dp[0][j] = 1;
			}
			else if (obstacleGrid[0][j] == 1) {
				flag = true;
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (obstacleGrid[i][j] == 1) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
				}
			}
		}
		return dp[m - 1][n - 1];
    }
}

发表于 2020-08-02 16:13:09 回复(0)

Java

Fubuki_0v0

public int uniquePathsWithObstacles (int[][] obstacleGrid) {
// write code here
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] recode = new int[m][n];
recode[0][0] = 1;
for(int x=0; x<m; x++) {
for(int y=0; y<n; y++) {
if(obstacleGrid[x][y]==1) { //有障碍，到达该点方案数直接设置为0
recode[x][y]=0;
continue;
}
if(x-1>=0) {
recode[x][y]+=recode[x-1][y];
}
if(y-1>=0) {
recode[x][y]+=recode[x][y-1];
}
}
}
return recode[m-1][n-1];
}

发表于 2020-07-13 20:10:00 回复(0)

Java

悟Kong

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null)
            return 0;
        int i,j;
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][]f=new int[m][n];
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        else{
            f[0][0]=1;
        }
                    
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                if(obstacleGrid[i][j]==1){
                   f[i][j]=0;
                   continue; 
                }
                if(i==0&&j!=0){
                    f[i][j]=f[i][j-1];
                }
                if(i!=0&&j==0){
                    f[i][j]=f[i-1][j];
                }
                if(i!=0&&j!=0){
                    f[i][j]=f[i-1][j]+f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }
}

发表于 2020-03-16 11:47:51 回复(0)

Java

力喜

java实现，运行时间：95ms占用内存：12364k。动态规划算法。与上一道路径总数思路相同，先写状态方程：M(x,y)=M(x-1,y)+M(x,y-1)。

而如果坐标(x,y)处有障碍，那么从(0,0)到达(x,y)处的路径数为0，而需要注意是，如果矩阵的边边处(i==0或j==0)有障碍，那么该边障碍及以后的元素的方法数都应置为0，（如果不这么置，矩形边边元素赋值时将会报错数组越界。）后续再用状态方程求方法数。

如{0,0}

{1,1}

{0,0}的Method数组应是：{{0,0},

{0,0}

{0,0}};

{0,0}

{1,0}的Method数组应是：先是{0,1}

{0,0}, 再由状态方程，锝Method数组为：{0,1}

{0,1}

而边边元素的赋值应分别遍历 i 和 j ，首先数组元素的默认值为0，因此，当遍历到的obstacleGrid[i][j]为0时，才给Method[i][j]赋值为1，一旦边边有障碍物，该行都为0；可以写成：

for(int i=0;i<length&&obstacle[0][i]==0;i++)
    method[i][j]=1;

那么，一旦出现obstacle[i][j]==1,就不会进循环，那么Method元素的值就为默认值0。

或者写成

for(int i=0;i<length;i++)
{if(obstacle[i][0]==0) method[i][0]=1;
 else break; }

一旦有障碍，障碍和后面的都跳出循环，即为默认值0.。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int length = obstacleGrid.length;
        int width = obstacleGrid[0].length;
int[][]method=new int[length][width];
int lflag=0;
int wflag=0;
//obstacleGrid矩阵边边全为 0 时，赋值为1；遇到边边有障碍，它以后的值为默认值0，不需要赋值。
for(int i=0;i<length;i++)
{if(obstacleGrid[i][0]==0) method[i][0]=1;
else break;}

for(int j=0;j<width;j++)
{if(obstacleGrid[0][j]==0) method[0][j]=1;
else break;}

for(int i=1;i<length;i++)
{    for(int j=1;j<width;j++)
    {
        if(obstacleGrid[i][j]==1) method[i][j]=0;
        else method[i][j]=method[i-1][j]+method[i][j-1];
    }}

return method[length-1][width-1];

    }}

编辑于 2019-08-17 20:05:29 回复(0)

Java

成小呆

// 首先初始化(0,0)=1表示从起点到(0,0)有1条路
// 遍历数组
//     如果(x,y)的值是1(障碍),将其值置为0表示从起点到这里没有一条路可以走通
//     如果(x,y)的值是0(空地),他的值为(x-1, y) + (x, y-1),因为只能向右走或者向下走,能达到某一点的路径总和等于它左边的路径总和加上它上边的路径总和
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;
        obstacleGrid[0][0] ^= 1;
        for (int i = 0 ; i < obstacleGrid.length ; i ++) {
            for (int j = 0 ; j < obstacleGrid[0].length ; j ++) {
                if (i == 0 && j == 0) continue;
                if (obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                else if (i == 0) obstacleGrid[i][j] = obstacleGrid[i][j-1];
                else if (j == 0) obstacleGrid[i][j] = obstacleGrid[i-1][j];
                else obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}

发表于 2019-07-17 00:26:09 回复(0)

Java

bomnana

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][] dp = new int[m][n];
        dp[0][0] = 1-obstacleGrid[0][0];//初始化
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++ ){
      //该句可以避免无用功，如果是阻碍点直接丢弃，进入下一个点，同时dp[i][j]=0不影响
                
                if(obstacleGrid[i][j]==0){
                    if(i==0 && j!=0)
                        dp[0][j] = dp[0][j-1];//右赋值
                    else if(i!=0 && j==0)
                        dp[i][0] = dp[i-1][0];//左赋值
                    else if(i!=0 && j!=0)
                        dp[i][j]=dp[i-1][j]+dp[i][j-1];//左+上赋值
                    else
                        continue;
                }
            }
        return dp[m-1][n-1];
    }
}

空间换时间，重新搭建一个矩阵，将不能通过的地方为0，边界上的点通过后一个点根据前一个点进行计算，其他的点则通过上，左进行计算

编辑于 2019-05-06 13:56:03 回复(0)

Java

jRomann

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m =obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid==null || m==0 || n==0) return 0;
        
        int[][]res = new int[m][n];
        //res[0][0] = obstacleGrid[0][0];
        for(int i = 0;i<n;i++){
            if(obstacleGrid[0][i]==0)
            res[0][i] = 1 ;
            else
                break;
        }
        for(int i = 0;i<m;i++){
            if(obstacleGrid[i][0]==0)
            res[i][0] = 1 ;
            else
                break;
        }
        for(int i = 1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==0)
                res[i][j] = res[i-1][j]+res[i][j-1];
                else
                    res[i][j] =0;
            }
        }
        return res[m-1][n-1];
    }
}

发表于 2018-06-30 17:15:25 回复(0)

Java

昵称好难取

public class Solution {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length, n = obstacleGrid[0].length;

        if(obstacleGrid[m-1][n-1] == 1) return 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    obstacleGrid[i][j] = -1;
            }
        }

        for (int i = m - 1; i >= 0; i--) {

            if (obstacleGrid[i][n - 1] == -1) {
                for(int j = i; j >= 0; j--) {
                    obstacleGrid[j][n - 1] = 0;
                }
                break;
            }
            obstacleGrid[i][n - 1] = 1;
        }
        for (int i = n - 1; i >= 0; i--) {

            if (obstacleGrid[m-1][i] == -1) {
                for(int j = i; j >= 0; j--) {
                    obstacleGrid[m-1][j] = 0;
                }
                break;
            }
            obstacleGrid[m - 1][i] = 1;
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2 ; j >= 0; j--) {
                if (obstacleGrid[i][j] == -1) {
                    obstacleGrid[i][j] = 0;
                    continue;
                }
                obstacleGrid[i][j] = obstacleGrid[i+1][j] + obstacleGrid[i][j+1];
            }
        }

        return obstacleGrid[0][0];
    }
}

发表于 2018-04-01 20:15:54 回复(0)

Java

Holiday_12138

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] arr = new int[n];
        for(int i=0; i<n && obstacleGrid[0][i] != 1; i++)
            arr[i] = 1;
        for(int i = 1 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++)
                if(i * j !=0)
                    arr[j] = obstacleGrid[i][j] == 1? 0 : arr[j]+arr[j-1];
        		else
                    arr[j] = obstacleGrid[i][j] == 1? 0 : arr[j];
        return arr[n-1];
    }
}

发表于 2017-06-20 21:14:29 回复(0)

Java

城市里的养猫者

public int uniquePathsWithObstacles(int[][] obstacleGrid) { int width = obstacleGrid[0].length; int[] dp = new int[width];
    dp[0] = 1; for (int[] row : obstacleGrid) { for (int j = 0; j < width; j++) { if (row[j] == 1)
                dp[j] = 0; else if (j > 0)
                dp[j] += dp[j - 1];
        }
    } return dp[width - 1];
}

发表于 2017-03-12 12:21:13 回复(0)

Java

詆調壹點

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
		for (int i = 0; i < dp.length; i ++ ) {
			if(obstacleGrid[i][0] == 1) break;
			dp[i][0] = 1;
		}
		for (int i = 0; i < dp[0].length; i ++ ) {
			if(obstacleGrid[0][i] == 1) break;
			dp[0][i] = 1;
		}
		for (int i = 1; i < dp.length; i ++ ) {
			for (int j = 1; j < dp[0].length; j ++ ) {
				if(obstacleGrid[i][j] == 1) dp[i][j] = 0;
				else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		return dp[dp.length - 1][dp[0].length - 1];
	}
}

发表于 2016-11-05 17:35:32 回复(2)