We can model this problem as a graph (grid) problem. We can use BFS to find the shortest path, but we need to consider the teleportation. Walking to a neighbor costs 1 step, teleporting via a portal costs 0 step (but can be used at most once per letter), our grid becomes a weighted graph with edge weight only 0 or 1. A plain BFS assumes all edges have the same weight, and Dijkstra's algorithm with priority queue works but adds extra complexity, so 0-1 BFS is the perfect middle ground:
The grid has exactly two weights:
- Teleport:
0 - Normal walk:
1
- When traversing to a neighbor, we enqueue at the end of queue as normal BFS, since it's a normal movement.
- When traversing to portal, we enqueue at first of queue, since teleportation doesn't count as a normal movement, it stays in the same layer of current position, we explore it immediately at the same "level".
Based on the key insights, we can implement the 0-1 BFS with precomputing portals.
- We use hash map to store the portals for each letter, and a boolean array to track if we have used the portal for each letter.
- Define a matrix to track the distance to each cell, relax and enqueue when we find a shorter path. This is the same as 542. 01 Matrix.
- We have to process the portal
fun minMoves(matrix: Array<String>): Int {
val m = matrix.size
val n = matrix.first().length
// Pre-compute the portals positions
val usedPortal = BooleanArray(26)
val portals = Array(26) { mutableListOf<Pair<Int, Int>>() }
for (i in 0 until m) {
for (j in 0 until n) {
val c = matrix[i][j]
if (c in 'A'..'Z') portals[c - 'A'].add(i to j)
}
}
val distance = Array(m) { IntArray(n) { Int.MAX_VALUE } }
val queue = ArrayDeque<Pair<Int, Int>>()
queue.addLast(0 to 0)
distance[0][0] = 0
while (queue.isNotEmpty()) {
val (x, y) = queue.removeFirst()
val c = matrix[x][y]
// Process portal (weight 0)
if (c in 'A'..'Z' && usedPortal[c - 'A'].not()) {
val p = portals[c - 'A']
for (i in p.indices) {
val (px, py) = p[i]
if (distance[px][py] > distance[x][y]) {
distance[px][py] = distance[x][y]
// NOTE: Enqueue the portal at the first of queue
queue.addFirst(px to py)
}
}
usedPortal[c - 'A'] = true
}
// Normal walk (weight 1): General implementation of BFS for shortest path
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (newX in 0 until m && newY in 0 until n && matrix[newX][newY] != '#') {
if (distance[newX][newY] > distance[x][y] + 1) {
distance[newX][newY] = distance[x][y] + 1
// Enqueue the adjacent node at the end of queue
queue.addLast(newX to newY)
}
}
}
}
val ans = distance[m - 1][n - 1]
return if (ans == Int.MAX_VALUE) -1 else ans
}- Time Complexity:
O(m * n + P), we visit each cell at most once, and process each portal at most once. - Space Complexity:
O(m * n + P), we use a matrix to track the distance to each cell, and a hash map to store the portals for each letter.
source -> ... weight 0 -> destination
-> ... weight 1 -> destination
...
-> ... weight 5 -> destination