55 lines
1.5 KiB
Kotlin
55 lines
1.5 KiB
Kotlin
|
class Solution {
|
||
|
|
private data class Position(val x: Int, val y: Int) {
|
||
|
|
operator fun plus(rhs: Position): Position = Position(x + rhs.x, y + rhs.y)
|
||
|
|
}
|
||
|
|
|
||
|
|
companion object {
|
||
|
|
private val DIRECTIONS =
|
||
|
|
listOf(
|
||
|
|
Position(0, 1),
|
||
|
|
Position(0, -1),
|
||
|
|
Position(1, 0),
|
||
|
|
Position(-1, 0),
|
||
|
|
)
|
||
|
|
}
|
||
|
|
|
||
|
|
private fun isValid(
|
||
|
|
grid: Array<IntArray>,
|
||
|
|
p: Position,
|
||
|
|
): Boolean =
|
||
|
|
(
|
||
|
|
p.y >= 0 && p.y < grid.size && p.x >= 0 && p.x < grid[p.y].size
|
||
|
|
)
|
||
|
|
|
||
|
|
fun minimumObstacles(grid: Array<IntArray>): Int {
|
||
|
|
val (rows, cols) = grid.size to grid[0].size
|
||
|
|
|
||
|
|
val dp = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }
|
||
|
|
dp[0][0] = 0
|
||
|
|
|
||
|
|
val deque = ArrayDeque<Pair<Position, Int>>()
|
||
|
|
deque.addLast(Position(0, 0) to 0)
|
||
|
|
|
||
|
|
while (!deque.isEmpty()) {
|
||
|
|
val (position, obstacles) = deque.removeFirst()
|
||
|
|
|
||
|
|
DIRECTIONS.forEach { dir ->
|
||
|
|
val next = position + dir
|
||
|
|
if (!isValid(grid, next) || dp[next.y][next.x] != Int.MAX_VALUE) {
|
||
|
|
return@forEach
|
||
|
|
}
|
||
|
|
|
||
|
|
if (grid[next.y][next.x] == 1) {
|
||
|
|
dp[next.y][next.x] = obstacles + 1
|
||
|
|
deque.addLast(next to obstacles + 1)
|
||
|
|
} else {
|
||
|
|
dp[next.y][next.x] = obstacles
|
||
|
|
deque.addFirst(next to obstacles)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return dp[rows - 1][cols - 1]
|
||
|
|
}
|
||
|
|
}
|