首页 > 试题广场 >

求路径 ii

[编程题]求路径 ii
  • 热度指数：15975 时间限制：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]]

输出

0
示例2

输入

[[1],[1]]

输出

0
算法知识视频讲解
添加回答
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头像 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头像 悟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头像 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头像 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头像 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)
提交观点

问题信息

动态规划
难度：
11条回答 25898浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求路径 ii

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号