980.unique-paths-iii.md

980. Unique Paths III

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

private var count = 0

private val directions = arrayOf(
    intArrayOf(-1, 0),
    intArrayOf(1, 0),
    intArrayOf(0, -1),
    intArrayOf(0, 1)
)

fun uniquePathsIII(grid: Array<IntArray>): Int {
    var startX = 0
    var startY = 0
    var walkOver = 0
    for (i in 0 until grid.size) {
        for (j in 0 until grid[0].size) {
            if (grid[i][j] == 1) {
                startX = i
                startY = j
            }
            if (grid[i][j] != -1) walkOver++
        }
    }
    dfs(grid, startX, startY, hashSetOf<Pair<Int, Int>>(), walkOver)
    return count
}

private fun dfs(grid: Array<IntArray>, x: Int, y: Int, visited: HashSet<Pair<Int, Int>>, walkOver: Int) {
    if (x < 0 || x >= grid.size || y < 0 || y >= grid[0].size || grid[x][y] == -1 || visited.contains(x to y)) return 
    visited.add(x to y)
    if (grid[x][y] == 2) {
        if (visited.size == walkOver) count++
        visited.remove(x to y)
        return
    }
    
    directions.forEach { d ->
        val newX = x + d[0]
        val newY = y + d[1]
        dfs(grid, newX, newY, visited, walkOver)
    }
    visited.remove(x to y)
}

• Time Complexity: O(4^(m + n)).
• Space Complexity: O(m * n).