#3552

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Grid Teleportation Traversal

Find the minimum moves to traverse a 2D grid using standard steps and one-time portal teleports efficiently.

array hash table breadth first search matrix

Problem Statement

You are given a 2D grid matrix of size m x n where each cell is either an empty cell '.', an obstacle '#', or an uppercase letter representing a portal. You start at the top-left corner (0, 0) and aim to reach the bottom-right corner (m - 1, n - 1) using the fewest moves. You may move up, down, left, or right to adjacent cells that are within bounds and not blocked by obstacles.

When you step on a cell containing a portal letter, you may teleport instantly to any other cell with the same letter if you have not used that portal before. Each portal letter can be used at most once during your journey, and teleportation does not count as a move. Determine the minimum number of moves required to reach the target or return -1 if it is impossible.

Examples

Example 1

Input: matrix = ["A..",".A.","..."]

Output: 2

Example 2

Input: matrix = [".#...",".#.#.",".#.#.","...#."]

Output: 13

Constraints

1 <= m == matrix.length <= 103
1 <= n == matrix[i].length <= 103
matrix[i][j] is either '#', '.', or an uppercase English letter.
matrix[0][0] is not an obstacle.

Solution Approach

Preprocess portal positions

Scan the grid once to record all coordinates for each portal letter in a hash map. This allows O(1) access to any portal destinations during BFS, avoiding repeated linear searches across the matrix.

Breadth-first search with portals

Use a queue to perform BFS from the starting cell, tracking visited cells and used portals. When encountering a portal, push all its destinations onto the queue if the portal letter hasn't been used yet. This treats portals as connected super-nodes while maintaining correct move counts.

Handle obstacles and boundaries

Before moving to any adjacent cell or teleport destination, check if it is within grid bounds and not an obstacle. Mark visited cells and used portals to prevent cycles and redundant exploration, ensuring BFS finds the minimum move path efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n + total portal connections), as each cell is processed once and each portal super-node is expanded once. Space complexity is O(m n + number of portals) to store visited states and portal mappings.

What Interviewers Usually Probe

Watch for repeatedly scanning the entire matrix for portals, which increases runtime.
Verify BFS handles one-time portal usage correctly to avoid overcounting moves.
Consider edge cases where portals lead to dead ends or the target is unreachable.

Common Pitfalls or Variants

Common pitfalls

Failing to mark portals as used after first teleport can cause infinite loops.
Forgetting to check grid boundaries before moving results in index errors.
Assuming teleportation counts as a move, which inflates the path length incorrectly.

Follow-up variants

Allow portals to be used multiple times, turning the problem into standard multi-source BFS.
Restrict movement to only horizontal or vertical directions but no diagonal, increasing path constraints.
Introduce weighted moves where teleportation has a cost greater than zero, changing BFS to Dijkstra.

FAQ

How do portals affect the minimum move calculation in Grid Teleportation Traversal?

Each portal letter acts as a one-time teleport connection to all matching cells. BFS must treat these as super-nodes and ensure each letter is used at most once to correctly compute minimum moves.

Can I revisit a cell after using a portal in this problem?

Yes, you can revisit cells, but the portal letter can only be used once. Subsequent visits must use standard adjacent moves.

What is the recommended data structure to track portals efficiently?

A hash map mapping each portal letter to a list of its cell coordinates allows O(1) access during BFS for teleportation.

How does GhostInterview ensure I don't miss edge cases?

It visualizes BFS exploration including portal usage and obstacles, immediately showing if paths are blocked or incorrectly counted.

What is the primary pattern used in this problem?

Array scanning plus hash lookup, combined with BFS to handle both standard moves and portal super-nodes efficiently.

terminal

Solution

Solution 1: 0-1 BFS

We can use 0-1 BFS to solve this problem. We start from the top-left cell and use a double-ended queue to store the coordinates of the current cell. Each time we dequeue a cell, we check its four adjacent cells. If an adjacent cell is an empty cell and has not been visited, we add it to the queue and update its distance.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        m, n = len(matrix), len(matrix[0])
        g = defaultdict(list)
        for i, row in enumerate(matrix):
            for j, c in enumerate(row):
                if c.isalpha():
                    g[c].append((i, j))
        dirs = (-1, 0, 1, 0, -1)
        dist = [[inf] * n for _ in range(m)]
        dist[0][0] = 0
        q = deque([(0, 0)])
        while q:
            i, j = q.popleft()
            d = dist[i][j]
            if i == m - 1 and j == n - 1:
                return d
            c = matrix[i][j]
            if c in g:
                for x, y in g[c]:
                    if d < dist[x][y]:
                        dist[x][y] = d
                        q.appendleft((x, y))
                del g[c]
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if (
                    0 <= x < m
                    and 0 <= y < n
                    and matrix[x][y] != "#"
                    and d + 1 < dist[x][y]
                ):
                    dist[x][y] = d + 1
                    q.append((x, y))
        return -1

Continue Practicing

#3568 minimum moves to clean the classroom #3548 equal sum grid partition ii #3607 power grid maintenance