Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and space is marked as 1 and 0 respectively in the grid.

Source

package questions

import _utils.UseCommentAsDocumentation
import utils.shouldBe

/**
 * A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
 * The robot can only move either down or right at any point in time.
 * The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
 * Now consider if some obstacles are added to the grids. How many unique paths would there be?
 * An obstacle and space is marked as 1 and 0 respectively in the grid.
 *
 * <img src="https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg" height="200" width="200"/>
 *
 * [Source](https://leetcode.com/problems/unique-paths-ii/)
 */
@UseCommentAsDocumentation
private interface UniquePathsII {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int
}

private class UniquePathsIINaiveApproach : UniquePathsII {
    private enum class Dir { R, D }

    private var answer = 0
    private lateinit var grid: Array<IntArray>

    override fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        if (obstacleGrid[obstacleGrid.lastIndex][obstacleGrid[0].lastIndex] == 1) {
            return 0
        }
        if (obstacleGrid[0][0] == 1) {
            return 0
        }
        this.grid = obstacleGrid
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        if (m == 1 && n == 1) return 1
        traverse(Dir.R, 0, 0, m - 1, n - 1) // go right
        traverse(Dir.D, 0, 0, m - 1, n - 1) // go down
        return answer
    }


    private fun traverse(direction: Dir, posX: Int, posY: Int, rowMaxIndex: Int, colMaxIndex: Int) {
        if (direction == Dir.R) {
            val newPositionX = posX + 1
            if (!canMoveHere(row = posY, col = newPositionX)) {
                return
            }
            if (newPositionX == colMaxIndex && posY == rowMaxIndex) {
                answer++
            } else {
                traverse(Dir.R, newPositionX, posY, rowMaxIndex, colMaxIndex)
                traverse(Dir.D, newPositionX, posY, rowMaxIndex, colMaxIndex)
            }
        } else {
            val newPositionY = posY + 1
            if (!canMoveHere(row = newPositionY, col = posX)) {
                return
            }
            if (posX == colMaxIndex && newPositionY == rowMaxIndex) {
                answer++
            } else {
                traverse(Dir.R, posX, newPositionY, rowMaxIndex, colMaxIndex)
                traverse(Dir.D, posX, newPositionY, rowMaxIndex, colMaxIndex)
            }
        }
    }

    private fun canMoveHere(row: Int, col: Int): Boolean {
        val cell = this.grid.getOrNull(row)?.getOrNull(col)
        if (cell == 0) return true
        if (cell == 1 || cell == null) return false
        return true
    }
}


private class UniquePathsIINaiveArrayOfArray : UniquePathsII {
    override fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        if (obstacleGrid[obstacleGrid.lastIndex][obstacleGrid[0].lastIndex] == 1) {
            return 0
        }
        if (obstacleGrid[0][0] == 1) {
            return 0
        }
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        val dp = Array<IntArray>(m) {
            IntArray(n) { 0 }
        }

        for (row in 0..dp.lastIndex) {
            for (col in 0..dp[0].lastIndex) {
                if (obstacleGrid[row][col] == 1) {
                    dp[row][col] = 0
                } else if (row == 0 && col == 0) {
                    dp[row][col] = 1 // only one way to get to (0,0) is moving left
                } else if (row == 0) {
                    dp[row][col] = dp[row][col - 1] // only way to get to first row is move up
                } else if (col == 0) {
                    dp[row][col] = dp[row - 1][col] // only way to get to left col is move left
                } else {
                    dp[row][col] = dp[row - 1][col] + dp[row][col - 1] // two ways
                }
            }
        }
        return dp[m - 1][n - 1]
    }
}


fun main() {
    val uniquePathCheck: (input: Array<IntArray>, expected: Int) -> Int? = { input, expected ->
        UniquePathsIINaiveApproach().uniquePathsWithObstacles(input) shouldBe
                UniquePathsIINaiveArrayOfArray().uniquePathsWithObstacles(input) shouldBe expected
    }

    uniquePathCheck.invoke(arrayOf(intArrayOf(1, 0)), 0)

    run {

        val input = arrayOf(
            intArrayOf(0, 0),
            intArrayOf(1, 1),
            intArrayOf(0, 0)
        )
        uniquePathCheck.invoke(input, 0)
    }

    uniquePathCheck.invoke(
        arrayOf(
            intArrayOf(0, 0, 0),
            intArrayOf(0, 1, 0),
            intArrayOf(0, 0, 0)
        ),
        2
    )

    uniquePathCheck.invoke(
        arrayOf(
            intArrayOf(0, 0, 0, 0),
            intArrayOf(0, 1, 0, 0),
            intArrayOf(0, 0, 0, 0),
            intArrayOf(0, 0, 1, 0),
            intArrayOf(0, 0, 0, 0),
        ),
        7
    )

}

---

View on GitHub

Updated on 2021-11-21