private val directions = arrayOf(
intArrayOf(-1, -1),
intArrayOf(-1, 0),
intArrayOf(-1, 1),
intArrayOf(0, -1),
intArrayOf(0, 1),
intArrayOf(1, -1),
intArrayOf(1, 0),
intArrayOf(1, 1)
)
fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
val n = grid.size
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1
var distance = 1
val queue = ArrayDeque<Pair<Int, Int>>()
val visited = HashSet<Pair<Int, Int>>()
queue.addLast(0 to 0)
visited.add(0 to 0)
while (queue.isNotEmpty()) {
val size = queue.size
repeat (size) {
val (x, y) = queue.removeFirst()
if (x == n - 1 && y == n - 1) return distance
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (newX !in 0 until n) continue
if (newY !in 0 until n) continue
if (visited.contains(newX to newY)) continue
if (grid[newX][newY] == 0) {
queue.addLast(newX to newY)
visited.add(newX to newY)
}
}
}
distance++
}
return -1
}
- Time Complexity:
O(n^2).
- Space Complexity:
O(n^2).