Leetcode:63. 不同路径 II-白红宇

Leetcode:63. 不同路径 II

阅读量：3710 次

发布时间：2019-05-21

本文共 1092 字，大约阅读时间需要 3 分钟。

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:[  [0,0,0],  [0,1,0],  [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右

解题思路：

还是标签法，设置data[y][x]数组记录(x,y)位置到终点的路劲数，初始值有墙的地方0，无墙的地方为1。从最后一列起开始往前遍历，每一列都是从下往上走，data[n][m]=1，当然如果data[n][m]有墙就直接返回0。递推式：

data[y][x]=data[y-1][x]+data[y][x-1];(注意数组溢出)。

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

转载地址：http://trfjn.baihongyu.com/

你可能感兴趣的文章