【每日一题】Day0006:CSDN每日一练：不同路径 II

【每日一题】Day0006:CSDN每日一练：不同路径 II

先放链接：

每日一练-做题 每日一练-做题https://dailycode.csdn.net/practice/1779831昨天发现CSDN上也有每日一练，感觉难度相对力扣简单一些，可能更适合自己现在的状态，颇感兴趣就尝试了一下。今天C/C++这道不同路径II很有意思，做完之后用Java实现并加上注释做为自己的理解和巩固。

代码如下：

package cn.daycode.csdncode;

public class UniquePathsWithObstacles {
    public static void main(String[] args) {
        int[][] grids = {{0,0,0,0,0},{0,1,1,0,0},{0,1,0,0,0},{0,1,0,0,0},{0,0,0,0,0}};
        int row_size = grids.length;
        int col_size = grids[0].length;

        System.out.println(uniquePathsWithObstacles(grids,row_size,col_size));

    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize){
        int row, col;
        int reset = 0;
        
        //根据只能往右走或往下走，如果第0列的某行值为1，则下面的所有值为1（障碍物）
        for (row = 0; row < obstacleGridRowSize; row++){ 
            if (reset == 1){
                obstacleGrid[row][0] = 1;
            }else{
                if (obstacleGrid[row][0] == 1) {
                    reset = 1;
                }
            }
        }
        reset = 0;
        //同理，第0行的某列为1开始，其他列都改为1
        for (col = 0; col < obstacleGridColSize; col++) { 
            if (reset == 1) {
                obstacleGrid[0][col] = 1;
            }else{
                if (obstacleGrid[0][col] == 1) {
                    reset = 1;
                }
            }
        }
        // 将修改后的数组，每一格的1改为0，0改为1，用于计算总路径
        for (row = 0; row < obstacleGridRowSize; row++) { 
            int[] line = obstacleGrid[row];
            for (col = 0; col < obstacleGridColSize; col++) {
                line[col] ^= 1;
            }
        }
        // 将每一格的值改为其左面一格和上面一格之和（从第二列第二行开始）
        for (row = 1; row < obstacleGridRowSize; row++) { 
            int[] last_line = obstacleGrid[row - 1];
            int[] line = obstacleGrid[row];
            for (col = 1; col < obstacleGridColSize; col++) {
                if(line[col] != 0) {
                    line[col] = line[col - 1] + last_line[col];
                }
            }
        }
        // 返回最右下角格最终的值就是最大路径数
        return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
    }
}