求路径 ii__牛客网

易水人去

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &a) {
        int i, j, m = a.size(), n = a[0].size();
        vector<vector<int> > dp(m, vector<int>(n, 0)); // 初始化成0
        // 第一个格点的值与障碍数相反
        dp[0][0] = 1 - a[0][0];
        // 依次计算
        for(i = 0; i < m; ++i) {
            for(j = 0; j < n; ++j) {
                // 只有没有障碍才有通路
                if(a[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]; // 左+上
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

发表于 2017-10-16 10:11:49 回复(5)

lxhao

public class Solution {
    //初始化两个for循环赋值可以免去,空间复杂度可以降到一维
    //个人觉得直接修改输入数据应该不是很合适的做法
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rowLen = obstacleGrid.length;
        int colLen = obstacleGrid[0].length;
        int[] res = new int[colLen + 1];
        res[1] = 1;
        for (int i = 1; i <= rowLen; i++) {
            for (int j = 1; j <= colLen; j++) {
                if (obstacleGrid[i - 1][j - 1] == 0) {
                    //res[i]保存的是上一行的值,当前值直接用左边的值加上上一行的值
                    res[j] += res[j - 1];
                } else {
                    res[j] = 0;
                }
            }
        }
        return res[colLen];
    }
}

编辑于 2017-08-06 13:10:06 回复(1)

找工作这么难啊！

出题出一半也是醉了

发表于 2020-08-26 09:57:50 回复(0)

C/C++

WZ_Dale

动态规划
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的路径数
F(i,j): 从(0,0)到达F(i,j)的路径数
状态递推：
F(i,j) = {F(i-1,j) + F(i,j-1)} OR {0, if obstacleGrid(i,j) = 1}
初始化：
特殊情况：第0行和第0列
F(0,i) = {1} OR {0, if obstacleGrid(0,j) = 1, j <= i}
F(i,0) = {1} OR {0, if obstacleGrid(j,0) = 1, j <= i}
返回结果：

F(m-1,n-1)

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        if(obstacleGrid.empty()){
            return 0;
        }
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> F(m, vector<int>(n, 0));
        for(int i = 0; i < m; ++i){
            if(obstacleGrid[i][0] == 1){
                break;
            }
            F[i][0] = 1;
        }
        for(int j = 0; j < n; ++j){
            if(obstacleGrid[0][j] == 1){
                break;
            }
            F[0][j] = 1;
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                if(obstacleGrid[i][j] == 1){
                    F[i][j] = 0;
                }
                else{
                    F[i][j] = F[i - 1][j] + F[i][j - 1];
                }
            }
        }
        return F[m - 1][n -1];
    }
};

发表于 2020-05-10 13:44:41 回复(0)

C/C++

努力的牛牛

    /*
    * 目的：找路径，找路径的拓展
    * 方法：动态规划
    */
    //方法一：使用二维dp，时间复杂度为O(n^2)，空间复杂度为O(n^2)
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int row = obstacleGrid.size();
        if (row==0) return 0;
        int col = obstacleGrid[0].size();
        vector<vector<int>>dp(row,vector<int>(col,1));
        for (int i = 0; i < row;++i){
            if (obstacleGrid[i][0] == 1){
                dp[i][0]=0;
            }
            else{
                dp[i][0] = i==0?1:dp[i-1][0];
            }
        }
        for (int j = 0; j <col;++j){
            if (obstacleGrid[0][j] == 1){
                dp[0][j] = 0;
            }
            else{
                dp[0][j] = j==0?1:dp[0][j-1];
            }
        }
        for (int i = 1; i < row;++i){
            for (int j = 1; j<col;++j){
                if (obstacleGrid[i][j] == 1){
                    dp[i][j] =  0;
                }
                else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[row-1][col-1];
    }
    //方法二:使用一维dp，时间复杂度O(n^2)，空间复杂度O(n)
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size(),n = obstacleGrid[0].size();
        vector<int>dp(n,0);
        dp[0] = 1;
        for (int i = 0; i < m; ++i){
            for (int j =0; j < n; ++j){
                if (obstacleGrid[i][j]==1)
                    dp[j]=0;
                else if (j>0){
                    dp[j] = dp[j]+dp[j-1];
                } 
            }
        }
        return dp[n-1];
    }

发表于 2019-12-09 19:50:41 回复(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)

maskwang

class Solution {
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        int dp[][] = new int[m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){

                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                    continue;
                }
                //初始化dp[0][0]
                if(i==0&&j==0){
                    dp[i][j]=1;
                    continue;
                }
                //第一行
                if(i==0){
                    dp[i][j]=dp[i][j-1];
                    continue;
                }
                //第一列
                if(j==0){
                    dp[i][j]=dp[i-1][j];
                    continue;
                }
                //上述情况之外
                dp[i][j]=dp[i-1][j]+dp[i][j-1];

            }
        }
        return dp[m-1][n-1];
    }
}

编辑于 2018-05-31 09:27:17 回复(0)

页川先生

    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]!=1)
                dp[i][0]=1;
            else
                break;
        }
        for(int j=0;j<n;j++){
            if(obstacleGrid[0][j]!=1)
                dp[0][j]=1;
            else
                break;
        }
        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-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

发表于 2017-11-02 10:31:47 回复(1)

C/C++

nbgao

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        if(n==0 || m==0)
        	return 0;
        	
        vector<int> dp(m,0);
        dp[0] = 1;
        for(int i=0;i<n;i++)
        	for(int j=0;j<m;j++)
        	{
        		if(obstacleGrid[i][j] == 1)
        			dp[j] = 0;
        		else if(j != 0)
        			dp[j] += dp[j-1];
			}
		return dp[m-1];
    }
};

发表于 2017-08-18 01:16:23 回复(0)

LinuX18

class Solution {
public:
  int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
  {
  /*
  int m=obstacleGrid.size(),n=obstacleGrid[0].size();
  if(obstacleGrid.empty())
        return 0;
  int dp[m][n];
  fill_n(&dp[0][0],m*n,0);
  dp[0][0] = obstacleGrid[0][0]==1? 0 : 1;
  for(int i=1;i<m;i++)
    dp[i][0] = obstacleGrid[i][0]==1 ? 0 : dp[i-1][0];
  for(int j=1;j<n;j++)
    dp[0][j] = obstacleGrid[0][j]==1 ? 0 : dp[0][j-1];
  for(int i=1;i<m;i++)
  {
      for(int j=1;j<n;j++)
      {
        dp[i][j] = obstacleGrid[i][j]==1 ? 0 : dp[i-1][j] + dp[i][j-1];
      }
  }
  return dp[m-1][n-1];
  }
  */
      
  /// 使用O(n)空间的方案
  int m=obstacleGrid.size(),n=obstacleGrid[0].size();
  if(m==0 || n==0)
    return 0;
  vector<int> res(n,0);
  res[0] = 1;
  for(int i=0;i<m;i++)
  {
      for(int j=0;j<n;j++)
      {
          if(obstacleGrid[i][j]==1)
            res[j] = 0;
          else if(j>0)
            res[j] = res[j]+res[j-1];
      }
  }
  return res[n-1];  
  }      
};

发表于 2017-07-14 22:30:03 回复(0)

Alex-大伟

package suda.alex.leetcode;

public class UniquePathsWithObstacles {

	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;
		int[][] dp = new int[m][n];
		for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++) {
			dp[i][0] = 1;
		}
		for (int j = 0; j < n && obstacleGrid[0][j] != 1; j++) {
			dp[0][j] = 1;
		}
		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];
	}
}

发表于 2016-11-03 23:10:36 回复(0)

revivedSuN

public class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
    	if(grid.length < 1 || grid[0].length < 1 || grid[0][0] == 1){
    		return 0;
    	}
    	int dp[] = new int[grid[0].length];
        dp[0] = 1;
    	for(int i = 1; i < grid[0].length; i++) {
    		dp[i] = grid[0][i] == 0 ? dp[i-1] : 0;
    	}
    	
    	for(int i = 1; i < grid.length; i++){
    		dp[0] = grid[i][0] != 1 ? dp[0] : 0;
    		for(int j = 1; j < grid[0].length; j++) {
    			dp[j] = grid[i][j] != 1 ? dp[j-1] + dp[j] : 0;
    		}
    	}
        return dp[grid[0].length - 1];
    }
}

发表于 2016-10-05 17:50:23 回复(0)

EasyLiu

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {

if(obstacleGrid.size()==0)

return 0;

int nRows=obstacleGrid.size();

int nColumns=obstacleGrid[0].size();

vector<vector<int> > dpPaths(nRows,vector<int>(nColumns));

//第一个

if(obstacleGrid[0][0]==0)//无障碍

dpPaths[0][0]=1;

else

dpPaths[0][0]=0;

//第一行

for(int i=1;i<nColumns;i++){

if(obstacleGrid[0][i]==1||dpPaths[0][i-1]==0)//前面走不通或者自己是障碍

dpPaths[0][i]=0;

else //无障碍

dpPaths[0][i]=1;

}

//第一列

for(int i=1;i<nRows;i++){

if(obstacleGrid[i][0]==1||dpPaths[i-1][0]==0)//前面走不通或者自己是障碍

dpPaths[i][0]=0;

else //无障碍

dpPaths[i][0]=1;

}

//中间部分

for(int i=1;i<nRows;i++){

for(int j=1;j<nColumns;j++){

if(obstacleGrid[i][j]==1)//有障碍

dpPaths[i][j]=0;

else

dpPaths[i][j]=dpPaths[i-1][j]+dpPaths[i][j-1];//无障碍

}

//返回结果

return dpPaths[nRows-1][nColumns-1];

}

};

发表于 2016-09-05 23:32:51 回复(0)

淡泊宁静吴传奇

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
    {
        if(obstacleGrid[0][0]==1)return 0;
        int a=obstacleGrid.size(),b=obstacleGrid[0].size();
        for(int i=0;i<a;++i)
        {
            if(obstacleGrid[i][0]==1)
            {
                for(;i<a;++i)
                    obstacleGrid[i][0]=0;
            }
            else obstacleGrid[i][0]=1;
        }
        for(int i=1;i<b;++i)
            if(obstacleGrid[0][i]==1)
            {
                for(;i<b;++i)
                    obstacleGrid[0][i]=0;
            }
            else obstacleGrid[0][i]=1;
        for(int i=1;i<a;++i)
            for(int j=1;j<b;++j)
        {
            if(obstacleGrid[i][j]==1)obstacleGrid[i][j]=0;
            else
                obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
        }   
        return obstacleGrid[a-1][b-1];
    }
};

发表于 2016-09-04 22:20:43 回复(0)

老石基

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

发表于 2016-06-03 21:44:39 回复(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)

C++

登临

int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {

int row=obstacleGrid.size();

int col=obstacleGrid[0].size();

obstacleGrid[0][0]=obstacleGrid[0][0]==0?1:0;

for(int i=1;i<col;i++)

{

if(obstacleGrid[0][i]==1)

{

obstacleGrid[0][i]=0;

}

else

{

obstacleGrid[0][i]=obstacleGrid[0][i-1];

}

for(int i=1;i<row;i++)

{

if(obstacleGrid[i][0]==1)

{

obstacleGrid[i][0]=0;

}

else

{

obstacleGrid[i][0]=obstacleGrid[i-1][0];

}

for(int i=1;i<row;i++)

{

for(int j=1;j<col;j++)

{

if(obstacleGrid[i][j]==1)

{

obstacleGrid[i][j]=0;

}

else

{

obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];

}

return obstacleGrid[row-1][col-1];

}

发表于 2023-03-24 00:00:36 回复(0)

C/C++

codewind

class Solution {
public:
    /**
     * 
     * @param obstacleGrid int整型vector<vector<>> 
     * @return int整型
     */
    int uniquePathsWithObstacles(vector<vector<int> >& g) {
        if(g.size()==0 || g[0].size()==0) return 0;
        // write code here
        int n = g.size(),m = g[0].size();
        vector<vector<int> >dp(n,vector<int>(m));
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j) {
                if(i==0&& j==0) {
                    dp[i][j] = g[i][j]==0;
                }else if(i==0) {
                    if(g[i][j]==0) dp[i][j] += dp[i][j-1];
                }else if(j==0) {
                    if(g[i][j]==0)
                        dp[i][j] +=dp[i-1][j];
                    
                }else {
                    if(g[i][j]==0) {
                        dp[i][j] += (dp[i-1][j]+dp[i][j-1]);
                    }
                }
            }
        }
        return dp[n-1][m-1];
        
    }
};

发表于 2021-04-11 20:43:18 回复(0)

无畏201901022203605

使用辅助二维数组，用于记录其每个F(i,j)的状态（[0,0] -> [i,j]的路径总数)，

对其先全部初始化为0，然后再对所给图的第一行和列遍历，在遇到障碍之前将所有状态置1，即存在仅一条路径到（0，i）和（i，0）,遇到障碍之后退出行列的初始化，初始化结束。这样第一行/列中的状态全部初始化完毕

从[1][1]下标开始进行更新处理，遇到obstacleGrid[i,j]为障碍时置0

int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        // write code here
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        int i, j;
        vector<vector<int>> graph(m, vector<int> (n,0));
        for (i = 0; i < m; i++)//对行列进行处理
        {
            if (obstacleGrid[i][0] != 1)
                graph[i][0] = 1;
            else
                break;
        }
        for (i = 0; i < n; i++)
        {
            if (obstacleGrid[0][i] != 1)
                graph[0][i] = 1;
            else
                break;
        }
        for (i = 1; i < m; i++)
        {//从[1][1]开始统计更新
            for (j = 1; j < n; j++)
            {
                graph[i][j] = graph[i - 1][j] + graph[i][j - 1];
                if (obstacleGrid[i][j] == 1)
                {
                    graph[i][j] = 0;
                }
            }
        }
        return graph[m - 1][n - 1];
    }

发表于 2021-03-21 17:19:34 回复(0)

C/C++

华科不平凡

设dp[i][j]表示前i行和前j列最短路径数，状态方程如下：

当i >= 2 && j >= 2时，
1. 如果obstacle[i-2][j-1] != 1, dp[i][j] += dp[i-1][j]
2. 如果obstacle[i-1][j-2] != 1, dp[i][j] += dp[i][j-1]
基准1: dp[1][k] = obstacle[0][k-1] != 1 && dp[1][k-1]!=0 ? 1 : 0
基准2: dp[k][1] = obstacle[k-1][0] != 1 && dp[k-1][1]!=0 ? 1 : 0

解释如下：

如果矩阵的列数行数都大于等于2，那么当前节点的最短路径数为左侧非阻塞节点的最短路径数+上侧非阻塞节点的最短路径数
基准1: 当行数为1时，当前节点的最短路径数为1或0，取决于左侧是否有阻隔
基准2: 当列数为1时，当前节点的最短路径数为1或0，取决于上侧是否有阻隔

代码如下：

//
// Created by jt on 2020/8/30.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param obstacleGrid int整型vector<vector<>>
     * @return int整型
     */
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        // write code here
        if (obstacleGrid.size() < 1 || obstacleGrid[0].size() < 1) return 0;
        vector<vector<int> > dp(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1, 0));
        if (obstacleGrid[0][0] == 0) dp[1][1] = 1;
        for (int i = 2; i <= obstacleGrid.size(); ++i) { dp[i][1] =  dp[i-1][1]!=0 && obstacleGrid[i-1][0]!=1 ? 1 : 0; }
        for (int i = 2; i <= obstacleGrid[0].size(); ++i) { dp[1][i] = dp[1][i-1]!=0 && obstacleGrid[0][i-1]!=1 ? 1 : 0; }
        for (int i = 2; i <= obstacleGrid.size(); ++i) {
            for (int j = 2; j <= obstacleGrid[0].size(); ++j) {
                dp[i][j] += obstacleGrid[i-2][j-1] == 0 ? dp[i-1][j] : 0;
                dp[i][j] += obstacleGrid[i-1][j-2] == 0 ? dp[i][j-1] : 0;
            }
        }
        return dp[obstacleGrid.size()][obstacleGrid[0].size()];
    }
};

发表于 2020-08-30 21:30:40 回复(0)

求路径 ii

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题