// https://leetcode.com/problems/unique-paths-ii
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
    val lastRowIndex = obstacleGrid.lastIndex
    val lastColIndex = obstacleGrid.first().lastIndex
    val hasObstacle = obstacleGrid[lastRowIndex][lastColIndex] == 1
    obstacleGrid[lastRowIndex][lastColIndex] = if (hasObstacle) 0 else 1
    for (rowIndex in lastRowIndex - 1 downTo 0) {
        val row = obstacleGrid[rowIndex]
        if (row[lastColIndex] == 1 || obstacleGrid[rowIndex + 1][lastColIndex] == 0) {
            row[lastColIndex] = 0
        } else {
            row[lastColIndex] = 1
        }
    }
    for (colIndex in lastColIndex - 1 downTo 0) {
        val row = obstacleGrid.last()
        if (row[colIndex] == 1 || row[colIndex + 1] == 0) {
            row[colIndex] = 0
        } else {
            row[colIndex] = 1
        }
    }
    for (rowIndex in lastRowIndex - 1 downTo 0) {
        for (colIndex in lastColIndex - 1 downTo 0) {
            if (obstacleGrid[rowIndex][colIndex] == 1) {
                obstacleGrid[rowIndex][colIndex] = 0
            } else {
                obstacleGrid[rowIndex][colIndex] = obstacleGrid[rowIndex + 1][colIndex] + obstacleGrid[rowIndex][colIndex + 1]
            }
        }
    }
    return obstacleGrid[0][0]
}

// https://leetcode.com/problems/unique-paths-ii
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
    val lastRowIndex = obstacleGrid.lastIndex
    val lastColIndex = obstacleGrid.first().lastIndex
    val hasObstacle = obstacleGrid[lastRowIndex][lastColIndex] == 1
    obstacleGrid[lastRowIndex][lastColIndex] = if (hasObstacle) 0 else 1
    for (rowIndex in lastRowIndex - 1 downTo 0) {
        val row = obstacleGrid[rowIndex]
        if (row[lastColIndex] == 1 || obstacleGrid[rowIndex + 1][lastColIndex] == 0) {
            row[lastColIndex] = 0
        } else {
            row[lastColIndex] = 1
        }
    }
    for (colIndex in lastColIndex - 1 downTo 0) {
        val row = obstacleGrid.last()
        if (row[colIndex] == 1 || row[colIndex + 1] == 0) {
            row[colIndex] = 0
        } else {
            row[colIndex] = 1
        }
    }
    for (rowIndex in lastRowIndex - 1 downTo 0) {
        for (colIndex in lastColIndex - 1 downTo 0) {
            if (obstacleGrid[rowIndex][colIndex] == 1) {
                obstacleGrid[rowIndex][colIndex] = 0
            } else {
                obstacleGrid[rowIndex][colIndex] = obstacleGrid[rowIndex + 1][colIndex] + obstacleGrid[rowIndex][colIndex + 1]
            }
        }
    }
    return obstacleGrid[0][0]
}
