Medium

Grid Teleportation Traversal

LAB

In a grid with S, E, # walls, . cells, and letter teleporters, return the shortest steps from S to E. Equal letters may teleport once per move.

EXAMPLES

Example 1

Input
{
  "grid": [
    "S.A",
    "###",
    "A.E"
  ]
}

Output
4

FUNCTION SHAPE

grid: stringArray→int

SOLUTION NOTE

Added the second dijkstras solution so you can compare.

The 0-1 BFS is pretty standard like I mentioned. The only interesting thing about this question is that we can teleport through portals that do not cost a move, so a 0 cost edge, otherwise moving is a 1 cost edge. And to keep track of which portals we have already used (we can use each at most once) we use a global array, instead of incorporating that into the state on the queue. This works, because think about how we greedily process the lowest cost path to reach the current node i every iteration. (ie. in dijkstra's) If we already used some letter, it doesn't make sense to save it for a later iteration, as that would achieve reaching the same node at a larger cost.

Reveal reference solution +

pythonREFERENCE

# 0-1 BFS Solution
def minMoves(self, matrix: List[str]) -> int:
    m, n = len(matrix), len(matrix[0])
    # Collect all portal positions
    portals = defaultdict(list)
    for i in range(m):
        for j in range(n):
            c = matrix[i][j]
            if 'A' <= c <= 'Z':
                portals[c].append((i, j))

    # dist[i][j] = best known #moves to reach (i,j)
    INF = 10**18
    dist = [[INF]*n for _ in range(m)]
    dist[0][0] = 0

    used = [False]*26  # used[ord(c)-ord('A')] == True once we've teleported via c
    dq = deque([(0, 0)])

    while dq:
        x, y = dq.popleft()
        d = dist[x][y]
        # If we reached the goal, we're done
        if x == m-1 and y == n-1:
            return d

        # 1) Teleport (cost = 0) — do this first so zero-cost edges are expanded immediately
        c = matrix[x][y]
        if 'A' <= c <= 'Z':
            idx = ord(c) - ord('A')
            if not used[idx]:
                used[idx] = True
                for tx, ty in portals[c]:
                    if dist[tx][ty] > d:
                        dist[tx][ty] = d
                        dq.appendleft((tx, ty))

        # 2) Regular moves (cost = 1)
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x+dx, y+dy
            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != '#':
                if dist[nx][ny] > d+1:
                    dist[nx][ny] = d+1
                    dq.append((nx, ny))

    # If unreachable
    return -1

# Dijkstra's Solution for comparison
def minMoves(self, matrix: List[str]) -> int:
    m, n = len(matrix), len(matrix[0])
    # Map each portal letter to its list of positions
    portals = defaultdict(list)
    for i in range(m):
        for j in range(n):
            c = matrix[i][j]
            if 'A' <= c <= 'Z':
                portals[c].append((i, j))

    # Distance matrix initialized to "infinite"
    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0

    # Track which portal letters have been used for teleport
    used_portal = [False] * 26

    # Min-heap for Dijkstra: (cost_so_far, x, y)
    heap = [(0, 0, 0)]

    while heap:
        d, x, y = heapq.heappop(heap)
        # If we've already found a better way here, skip
        if d > dist[x][y]:
            continue
        # If we reached the target, return the cost
        if x == m - 1 and y == n - 1:
            return d

        # 1) Teleport edges (cost 0)
        c = matrix[x][y]
        if 'A' <= c <= 'Z':
            idx = ord(c) - ord('A')
            if not used_portal[idx]:
                used_portal[idx] = True
                for tx, ty in portals[c]:
                    if dist[tx][ty] > d:
                        dist[tx][ty] = d
                        heapq.heappush(heap, (d, tx, ty))

        # 2) Regular adjacent moves (cost 1)
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != '#':
                nd = d + 1
                if dist[nx][ny] > nd:
                    dist[nx][ny] = nd
                    heapq.heappush(heap, (nd, nx, ny))

    # If destination is unreachable
    return -1

TimeO(m*n + P)

SpaceO(m*n)

Open on LeetCode ↗