【LeetCode-面试算法经典-Java实现】【063-Unique Paths II（唯一路径问题II）】
分类：LeetCode
【063-Unique Paths II（唯一路径问题II）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3×3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0]]
The total number of unique paths is 2. Note: m and n will be at most 100.
题目大意
唯一路径问题后续，如果路径中有障碍，求总的路径的种数。【唯一路径问题】 注意：网格的行数和列数都不超过100
解题思路
采用分治求解方法 用一个ｍ*n的组数A保存结果。 对于A数组中的元素有。 1、当x=0或者y=0时，并且(x, y)位置无障碍。有A[x][y] = 1； 有障碍就是0 2、当x>=1并且y>=1时，并且(x, y)位置无障碍。有A[x][y] = A[x-1][y]+A[x][y-1]。 有障碍就是0 3、所求的结点就是A[m-1][n-1]。
代码实现
算法实现类
public class Solution {(int[][] obstacleGrid) {// 输入校验if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1|| obstacleGrid[0][0] == 1|| obstacleGrid[obstacleGrid.length – 1][obstacleGrid[0].length – 1] == 1) {return 0;}int rows = obstacleGrid.length;int cols = obstacleGrid[0].length;int[][] result = new int[rows][cols];// 第一个位置有多少种方法，无障碍就是1种，有障碍就是0种result[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;for (int i = 1; i < cols; i++) {result[0][i] = obstacleGrid[0][i] == 0 ? result[0][i – 1] : 0;}for (int i = 1; i < rows; i++) {result[i][0] = obstacleGrid[i][0] == 0 ? result[i – 1][0] : 0;}for (int i = 1; i < rows; i++) {for (int j = 1; j < cols; j++) {result[i][j] = obstacleGrid[i][j] == 0 ? result[i – 1][j] + result[i][j – 1] : 0;}}return result[rows – 1][cols – 1];}(int[][] obstacleGrid) {// 输入校验if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1|| obstacleGrid[obstacleGrid.length – 1][obstacleGrid[0].length – 1] == 1) {return 0;}int[] result = {0};solve(obstacleGrid, 0, 0, result);return result[0];}(int[][] grid, int row, int col, int[] sum) {// 到达终点if (row == grid.length – 1 && col == grid[0].length – 1) {sum[0]++;}(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 0) {// 往右走solve(grid, row, col + 1, sum);// 往下走solve(grid, row + 1, col, sum);}}}评测结果
点击图片，鼠标不释放，拖动一段位置，，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇【LeetCode-面试算法经典-Java实现】【062-Unique Paths（唯一路径）】下一篇【LeetCode-面试算法经典-Java实现】【064-Minimum Path Sum（最小路径和）】
顶2踩0
世界上那些最容易的事情中，拖延时间最不费力。
