Facebook Pixel

3552. Grid Teleportation Traversal

MediumBreadth-First SearchArrayHash TableMatrix
Leetcode Link

Problem Description

You are given a 2D character grid matrix of size m x n, represented as an array of strings, where matrix[i][j] represents the cell at the intersection of the ith row and jth column. Each cell is one of the following:

  • '.' representing an empty cell.
  • '#' representing an obstacle.
  • An uppercase letter ('A'-'Z') representing a teleportation portal.

You start at the top-left cell (0, 0), and your goal is to reach the bottom-right cell (m - 1, n - 1). You can move from the current cell to any adjacent cell (up, down, left, right) as long as the destination cell is within the grid bounds and is not an obstacle.

If you step on a cell containing a portal letter and you haven't used that portal letter before, you may instantly teleport to any other cell in the grid with the same letter. This teleportation does not count as a move, but each portal letter can be used at most once during your journey.

Return the minimum number of moves required to reach the bottom-right cell. If it is not possible to reach the destination, return -1.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The problem asks for the minimum number of moves to reach the bottom-right cell on a grid with obstacles and special portal cells. Normally, we can explore the grid using Breadth-First Search (BFS), as it gives the shortest path in an unweighted grid. However, the portals add a twist: stepping on a portal lets you instantly travel to any other matching portal cell, but only once per portal letter.

To find the shortest path, treat a normal move to an empty cell as costing one move, and using a portal as costing zero moves since it's instantaneous. This fits the "0-1 BFS" model, where we use a double-ended queue to prioritize zero-cost moves (portals) over regular moves (adjacent steps). By tracking which portals have already been used, and always exploring all possible zero-cost (teleportation) moves before regular ones, we ensure we never miss a quicker path using portals. This idea leads us to an efficient way to compute the answer.

Solution Approach

This solution uses a 0-1 BFS (Breadth-First Search) strategy because the problem consists of two types of moves: adjacent cell moves that cost 1 step and instant portal jumps that cost 0 steps.

Key steps:

  • Portal Mapping: First, for each portal letter ('A' - 'Z') found in the grid, record all its coordinates in a dictionary. This allows instant lookup of all other positions for teleportation when stepping on a portal cell.

  • Distance Matrix: Maintain a 2D dist array representing the minimum number of moves to reach each cell. Initialize every cell with infinity (inf) except the starting cell at (0, 0), which is set to 0.

  • 0-1 BFS with Deque: Use a double-ended queue (deque) to perform BFS. This allows cells reached via a portal (cost 0) to be prioritized and processed earlier than regular moves (cost 1).

  • Move and Teleportation Logic: At each BFS step:

    • If on a portal cell (say letter 'A') and haven't used this portal yet, push all other cells with the same portal letter to the front of the queue, and set their distance equal to the current cell.
    • For normal adjacent cells, push them to the back of the queue with an incremented distance (+1).

  • Portal Use Tracking: Once a portal letter is used, remove it from the portal mapping. This ensures each portal is only used once, as required by the problem.

  • Termination: If the destination (m-1, n-1) is reached, return the associated distance. If the queue empties without reaching it, return -1 to indicate that it's impossible.

Summary: Using 0-1 BFS allows us to efficiently handle both move types and always find the shortest path. By managing portals as 0-cost transitions and ensuring once-only use per letter, the algorithm stays correct and efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small grid for illustration:

matrix = [
  ".A.",
  "#B#",
  ".A."
]
  • .: empty cell
  • #: obstacle
  • A and B: portal cells

Step-by-step 0-1 BFS Approach:

  1. Portal Mapping

    • 'A' is at (0,1) and (2,1)
    • 'B' is at (1,1)

  2. Initialization

    • dist[0][0]=0 (start at top-left)
    • All other distances set to infinity.
    • Deque starts with (0,0)
    • Unused portals: 'A', 'B'

  3. First BFS Loop

    • Current cell: (0,0), dist=0.
    • Check neighbors: (0,1) is 'A'. Move to (0,1): dist=1, enqueue to back. (1,0) is '#': obstacle, skip it.

  4. Next BFS Loop

    • Current cell: (0,1), dist=1
    • 'A' portal and unused. Teleport to (2,1) for free: enqueue (2,1) to front with dist=1.
    • Mark 'A' as used.
    • Check neighbors: (0,0) [already visited], (0,2) [empty], (1,1) is 'B'. Enqueue (0,2) and (1,1), both with dist=2.

  5. Next BFS Step: Portal Use

    • (2,1) dequeued from front, dist=1.
    • Neighbors: (1,1) is 'B' (already in queue), (2,0) and (2,2) are empty. Enqueue (2,0), (2,2) with dist=2.

  6. Continue BFS

    • (0,2) dequeued next. Neighbors are either obstacle or already visited.
    • (1,1) dequeued. This is portal 'B', but there are no other 'B' cells, so no teleportation happens.

  7. Last steps

    • (2,0) and (2,2) dequeued.
    • (2,2) is the bottom-right cell: reached at dist=2.

Result: The minimum number of moves is 2:

  • (0,0) → (0,1) [A] → teleport to (2,1) → (2,2)

This example illustrates how the 0-1 BFS explores zero-cost portal jumps before costlier steps, maps portal letters, and ensures each teleportation is only used once.

Solution Implementation

1from typing import List
2from collections import defaultdict, deque
3from math import inf
4
5class Solution:
6    def minMoves(self, matrix: List[str]) -> int:
7        rows, cols = len(matrix), len(matrix[0])
8
9        # Record all positions for each alphabetic teleport cell.
10        teleport = defaultdict(list)
11        for i, row in enumerate(matrix):
12            for j, char in enumerate(row):
13                if char.isalpha():
14                    teleport[char].append((i, j))
15
16        # Possible movement directions: up, right, down, left
17        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
18
19        # Distance matrix, initialized to infinity
20        dist = [[inf] * cols for _ in range(rows)]
21        dist[0][0] = 0
22
23        # BFS queue, starting from the top-left cell
24        queue = deque([(0, 0)])
25
26        while queue:
27            x, y = queue.popleft()
28            current_dist = dist[x][y]
29
30            # If destination (bottom-right) is reached, return the distance
31            if x == rows - 1 and y == cols - 1:
32                return current_dist
33
34            cell_value = matrix[x][y]
35
36            # Teleportation: If current cell is teleport and not already used
37            if cell_value in teleport:
38                for tx, ty in teleport[cell_value]:
39                    if current_dist < dist[tx][ty]:
40                        dist[tx][ty] = current_dist
41                        queue.appendleft((tx, ty))  # Prioritize teleportation (0-cost)
42                # Remove from teleport map to prevent re-use
43                del teleport[cell_value]
44
45            # Move to adjacent cells (cost +1)
46            for dx, dy in directions:
47                nx, ny = x + dx, y + dy
48                # Check boundaries and obstacles
49                if (
50                    0 <= nx < rows
51                    and 0 <= ny < cols
52                    and matrix[nx][ny] != '#'
53                    and current_dist + 1 < dist[nx][ny]
54                ):
55                    dist[nx][ny] = current_dist + 1
56                    queue.append((nx, ny))
57
58        # If goal is unreachable, return -1
59        return -1
60
1class Solution {
2    public int minMoves(String[] matrix) {
3        int m = matrix.length;
4        int n = matrix[0].length();
5
6        // Build mapping: character -> list of its coordinates in the matrix
7        Map<Character, List<int[]>> teleports = new HashMap<>();
8        for (int row = 0; row < m; row++) {
9            for (int col = 0; col < n; col++) {
10                char ch = matrix[row].charAt(col);
11                if (Character.isAlphabetic(ch)) {
12                    teleports.computeIfAbsent(ch, k -> new ArrayList<>())
13                        .add(new int[]{row, col});
14                }
15            }
16        }
17
18        // Directions: up, right, down, left
19        int[] dirs = {-1, 0, 1, 0, -1};
20        int INF = Integer.MAX_VALUE / 2;
21        int[][] distance = new int[m][n];
22        for (int[] arr : distance) Arrays.fill(arr, INF);
23
24        // BFS initialization
25        distance[0][0] = 0;
26        Deque<int[]> queue = new ArrayDeque<>();
27        queue.add(new int[]{0, 0});
28
29        while (!queue.isEmpty()) {
30            int[] curr = queue.pollFirst();
31            int currRow = curr[0];
32            int currCol = curr[1];
33            int currDist = distance[currRow][currCol];
34
35            // If destination reached, return answer
36            if (currRow == m - 1 && currCol == n - 1) return currDist;
37
38            char currChar = matrix[currRow].charAt(currCol);
39
40            // Teleport to all other cells with the same alphabet character
41            if (teleports.containsKey(currChar)) {
42                for (int[] pos : teleports.get(currChar)) {
43                    int tr = pos[0], tc = pos[1];
44                    if (currDist < distance[tr][tc]) {
45                        distance[tr][tc] = currDist; // teleportation doesn't increase step
46                        queue.addFirst(new int[]{tr, tc});
47                    }
48                }
49                teleports.remove(currChar); // Use teleportation only once per character
50            }
51
52            // Explore four directions
53            for (int d = 0; d < 4; d++) {
54                int nextRow = currRow + dirs[d];
55                int nextCol = currCol + dirs[d + 1];
56
57                // Check bounds and if not a wall ('#')
58                if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n &&
59                    matrix[nextRow].charAt(nextCol) != '#') {
60                    if (currDist + 1 < distance[nextRow][nextCol]) {
61                        distance[nextRow][nextCol] = currDist + 1;
62                        queue.addLast(new int[]{nextRow, nextCol});
63                    }
64                }
65            }
66        }
67        // No valid path to destination
68        return -1;
69    }
70}
71
1class Solution {
2public:
3    int minMoves(vector<string>& matrix) {
4        // Grid dimensions
5        int rows = matrix.size(), cols = matrix[0].size();
6
7        // Map from character to all its positions (used for teleportation)
8        unordered_map<char, vector<pair<int, int>>> teleport;
9        for (int i = 0; i < rows; ++i)
10            for (int j = 0; j < cols; ++j) {
11                char cell = matrix[i][j];
12                // Only consider alphabetic characters as teleporters
13                if (isalpha(cell))
14                    teleport[cell].emplace_back(i, j);
15            }
16
17        // Directions for moving: up, right, down, left
18        int dr[5] = {-1, 0, 1, 0, -1};
19
20        // Initialize distances to infinity
21        int INF = numeric_limits<int>::max() / 2;
22        vector<vector<int>> dist(rows, vector<int>(cols, INF));
23        dist[0][0] = 0;  // Start cell
24
25        // 0-1 BFS deque
26        deque<pair<int, int>> dq;
27        dq.emplace_back(0, 0);
28
29        while (!dq.empty()) {
30            auto [r, c] = dq.front();
31            dq.pop_front();
32            int d = dist[r][c];
33
34            // If reached the target cell, return the number of moves
35            if (r == rows - 1 && c == cols - 1)
36                return d;
37
38            // Teleportation: from current cell to all cells with same teleporter character
39            char cell = matrix[r][c];
40            if (teleport.count(cell)) {
41                for (auto [tr, tc] : teleport[cell]) {
42                    if (d < dist[tr][tc]) {
43                        dist[tr][tc] = d;  // Teleport (zero cost)
44                        dq.emplace_front(tr, tc);
45                    }
46                }
47                teleport.erase(cell);  // Process each teleporter just once
48            }
49
50            // Adjacent moves (cost 1)
51            for (int idx = 0; idx < 4; ++idx) {
52                int nr = r + dr[idx], nc = c + dr[idx + 1];
53                // Check boundaries and wall cells
54                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] != '#') {
55                    if (d + 1 < dist[nr][nc]) {
56                        dist[nr][nc] = d + 1;
57                        dq.emplace_back(nr, nc);
58                    }
59                }
60            }
61        }
62
63        // No possible way to reach target
64        return -1;
65    }
66};
67
1// Directions for moving up, right, down, left on the grid
2const directions = [-1, 0, 1, 0, -1];
3
4// Infinity value for unreachable cells
5const INF = Number.MAX_SAFE_INTEGER;
6
7/**
8 * Calculates the minimum number of moves needed to go from the top-left
9 * to the bottom-right cell in the matrix, considering teleportation by matching letters.
10 * @param matrix - Array of strings representing the grid
11 * @returns Minimum moves required, or -1 if unreachable
12 */
13function minMoves(matrix: string[]): number {
14    const rows = matrix.length;
15    const cols = matrix[0].length;
16
17    // Mapping each letter to all its positions on the grid
18    const teleports = new Map<string, [number, number][]>();
19    for (let i = 0; i < rows; i++) {
20        for (let j = 0; j < cols; j++) {
21            const char = matrix[i][j];
22            if (/^[A-Za-z]$/.test(char)) {
23                if (!teleports.has(char)) teleports.set(char, []);
24                teleports.get(char)!.push([i, j]);
25            }
26        }
27    }
28
29    // Distance matrix; fill with INF by default
30    const distance: number[][] = Array.from({ length: rows }, () => Array<number>(cols).fill(INF));
31    distance[0][0] = 0;
32
33    // Manual double-ended queue for 0-1 BFS
34    const queueCapacity = rows * cols * 2 + 5;
35    const deque = new Array<[number, number]>(queueCapacity);
36    let left = queueCapacity >> 1, right = queueCapacity >> 1;
37
38    // Queue operations
39    const pushFront = (val: [number, number]) => { deque[--left] = val; };
40    const pushBack = (val: [number, number]) => { deque[right++] = val; };
41    const popFront = (): [number, number] => deque[left++];
42    const isEmpty = () => left === right;
43
44    // Start from the top-left cell
45    pushBack([0, 0]);
46
47    // 0-1 BFS loop
48    while (!isEmpty()) {
49        const [curRow, curCol] = popFront();
50        const curDist = distance[curRow][curCol];
51
52        // If destination reached, return the answer
53        if (curRow === rows - 1 && curCol === cols - 1) return curDist;
54
55        const curChar = matrix[curRow][curCol];
56
57        // Teleport using the current letter (if any unvisited remain)
58        if (teleports.has(curChar)) {
59            for (const [nextRow, nextCol] of teleports.get(curChar)!) {
60                if (curDist < distance[nextRow][nextCol]) {
61                    distance[nextRow][nextCol] = curDist; // Teleportation, no extra cost
62                    pushFront([nextRow, nextCol]);
63                }
64            }
65            // Delete to avoid revisiting teleports of this letter
66            teleports.delete(curChar);
67        }
68
69        // Standard grid moves (up, right, down, left)
70        for (let d = 0; d < 4; d++) {
71            const newRow = curRow + directions[d];
72            const newCol = curCol + directions[d + 1];
73            // Check bounds and obstacles
74            if (
75                newRow >= 0 && newRow < rows &&
76                newCol >= 0 && newCol < cols &&
77                matrix[newRow][newCol] !== '#' &&
78                curDist + 1 < distance[newRow][newCol]
79            ) {
80                distance[newRow][newCol] = curDist + 1;
81                pushBack([newRow, newCol]);
82            }
83        }
84    }
85
86    // If the bottom-right cell is unreachable
87    return -1;
88}
89

Time and Space Complexity

  • Time Complexity: O(m * n) The BFS traverses each cell at most once. Each teleport operation (using matching characters) is also processed once per character due to deletion from g. Therefore, the total operations are bounded by the number of cells (m * n).

  • Space Complexity: O(m * n) The dist array and the queue q each take up to O(m * n) space. The dictionary g also stores at most O(m * n) positions corresponding to matching cells, leading the overall space to be O(m * n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More