Problem Description

You have a 2D grid of characters with m rows and n columns. Each cell in the grid contains one of three things:

• '.' - an empty cell you can walk through
• '#' - an obstacle you cannot pass through
• An uppercase letter 'A' to 'Z' - a teleportation portal

You start at the top-left corner (0, 0) and need to reach the bottom-right corner (m-1, n-1).

Movement Rules:

1. From any cell, you can move to an adjacent cell (up, down, left, or right) if:

   • The destination cell is within the grid boundaries
   • The destination cell is not an obstacle '#'
   • Each move to an adjacent cell counts as 1 move

2. When you step on a portal (a cell with a letter), you have the option to instantly teleport to any other cell in the grid that has the same letter:

   • Teleportation does not count as a move (it's free)
   • Each portal letter can only be used once for teleportation throughout your entire journey
   • After using a portal, you cannot teleport using that same letter again

Your task is to find the minimum number of moves needed to reach the destination. If it's impossible to reach the bottom-right corner, return -1.

For example, if you have two cells with letter 'A', when you reach one 'A', you can instantly teleport to the other 'A' for free, but after that, the 'A' portal is "used up" and cannot be used for teleportation again.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and edges connect adjacent cells. Additionally, portals create special edges between cells with the same letter.

Is it a tree?

• No: The grid graph has cycles (you can move in circles) and is not a tree structure.

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement and contains cycles, so it's not a DAG.

Is the problem related to shortest paths?

• Yes: We need to find the minimum number of moves to reach the destination, which is a shortest path problem.

Is the graph Weighted?

• No/Yes (special case): Regular moves have weight 1, but teleportation has weight 0. This is actually a 0-1 weighted graph, which is a special case that can be solved with modified BFS (0-1 BFS).

Since we have a 0-1 weighted graph (moves cost 1, teleportations cost 0), we arrive at BFS as our solution approach. Specifically, we use 0-1 BFS with a deque:

• When we teleport (cost 0), we add the destination to the front of the deque
• When we make a regular move (cost 1), we add the destination to the back of the deque

Conclusion: The flowchart leads us to use BFS, specifically the 0-1 BFS variant, which is perfect for finding the shortest path in a graph where edges have weights of either 0 or 1.

Intuition

The key insight is recognizing that this problem is essentially a shortest path problem with a twist - we have two types of moves with different "costs":

1. Regular moves to adjacent cells (cost = 1 move)
2. Teleportation through portals (cost = 0 moves)

This creates a 0-1 weighted graph scenario. In a standard BFS, all edges have the same weight, so we can use a regular queue. But here, since teleportation is "free," we need to prioritize exploring teleported positions before regular moves to ensure we find the optimal path.

Think of it this way: if you're at position A and can either walk to position B (1 move) or teleport to position C (0 moves), you should explore what's reachable from C first, because any path through C will always be shorter than or equal to paths through B.

This is why we use a deque (double-ended queue) instead of a regular queue:

• When we teleport (0 cost), we add the new position to the front of the deque - these positions get processed first
• When we make a regular move (1 cost), we add the new position to the back of the deque

Another crucial observation is that each portal can only be used once. Once we've teleported using letter 'A', we can never use any 'A' portal again. This prevents infinite loops and ensures our algorithm terminates. We track this by removing each portal letter from our dictionary after using it.

The distance tracking ensures we don't revisit cells with a worse path. If we've already reached a cell with distance d, we only process it again if we can reach it with a smaller distance. This optimization prevents redundant exploration and guarantees we find the shortest path.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation uses 0-1 BFS with a deque to handle the two different types of moves efficiently. Let's walk through the key components:

Data Structure Setup:

1. Portal Dictionary (g): We first scan the entire grid and create a dictionary where each key is a portal letter and the value is a list of all positions containing that letter. This allows O(1) lookup when we need to teleport.

2. Distance Matrix (dist): A 2D array initialized to infinity that tracks the minimum distance to reach each cell. We set dist[0][0] = 0 as our starting point.

3. Deque (q): A double-ended queue initialized with the starting position (0, 0).

BFS Process: The algorithm processes cells from the deque until either we reach the destination or the queue is empty:

1. Dequeue a cell (i, j) and get its current distance d.

2. Check if destination reached: If i == m-1 and j == n-1, return the distance.

3. Handle portal teleportation: If the current cell contains a portal letter c:

   • Iterate through all other positions with the same letter from g[c]
   • If we can reach any of these positions with a better distance (current distance d < stored distance), update the distance and add to the front of the deque using appendleft()
   • Delete the portal letter from the dictionary (del g[c]) to ensure it's only used once

4. Handle regular moves: Check all four adjacent cells using direction vectors:

   • For each valid adjacent cell (x, y) that is within bounds, not an obstacle, and can be reached with a better distance (d + 1 < dist[x][y]):
   • Update the distance to d + 1
   • Add to the back of the deque using append()

Why This Works:

• The deque ensures cells reached by teleportation (0 cost) are processed before cells reached by regular moves (cost 1)
• The distance matrix prevents revisiting cells with suboptimal paths
• Deleting used portals from the dictionary ensures each portal is used at most once
• The algorithm guarantees finding the shortest path because it explores all reachable cells in order of their distance from the start

If the queue becomes empty without reaching the destination, the function returns -1, indicating the destination is unreachable.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Grid (3x3):
. A #
. # A
. . .

Start: (0,0) → Goal: (2,2)

Initial Setup:

• Portal dictionary g = {'A': [(0,1), (1,2)]}
• Distance matrix initialized to infinity, except dist[0][0] = 0
• Deque q = [(0,0)]

Step 1: Process (0,0), distance = 0

• Current cell is '.', no portal to use
• Check adjacent cells:
  • Right (0,1): 'A', distance 0+1=1 < ∞, update dist[0][1]=1, append to back → q = [(0,1)]
  • Down (1,0): '.', distance 0+1=1 < ∞, update dist[1][0]=1, append to back → q = [(0,1), (1,0)]

Step 2: Process (0,1), distance = 1

• Current cell is 'A', portal available!
• Teleport to other 'A' at (1,2): distance 1+0=1 < ∞, update dist[1][2]=1, appendleft → q = [(1,2), (1,0)]
• Delete 'A' from portal dictionary: g = {}
• Check adjacent cells:
  • Left (0,0): already visited with better distance (0 < 2), skip
  • Right (0,2): '#' obstacle, skip

Step 3: Process (1,2), distance = 1 (processed first due to appendleft)

• Current cell is 'A', but portal already used (not in dictionary)
• Check adjacent cells:
  • Up (0,2): '#' obstacle, skip
  • Down (2,2): '.', distance 1+1=2 < ∞, update dist[2][2]=2, append to back → q = [(1,0), (2,2)]

Step 4: Process (1,0), distance = 1

• Current cell is '.', no portal
• Check adjacent cells:
  • Up (0,0): already visited with better distance (0 < 2), skip
  • Right (1,1): '#' obstacle, skip
  • Down (2,0): '.', distance 1+1=2 < ∞, update dist[2][0]=2, append to back → q = [(2,2), (2,0)]

Step 5: Process (2,2), distance = 2

• Destination reached! Return 2

The minimum path: (0,0) → (0,1) → teleport to (1,2) → (2,2) = 2 moves

Notice how the teleportation from (0,1) to (1,2) cost 0 moves, and by using appendleft, we prioritized exploring from (1,2) before (1,0), allowing us to find the optimal path quickly.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses BFS to traverse the matrix. Each cell can be visited at most twice:

• Once through normal BFS traversal (moving to adjacent cells)
• Once through teleportation when encountering a letter cell

The key optimization is using del g[c] after processing teleportation points, ensuring each group of letter cells is processed only once. Since we have at most m × n cells and each cell is processed a constant number of times, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The space usage includes:

• dist matrix: O(m × n) to store distances to each cell
• g dictionary: O(m × n) in worst case if all cells contain letters
• BFS queue q: O(m × n) in worst case when all cells are enqueued
• Other variables use constant space

Therefore, the total space complexity is O(m × n), where m and n are the number of rows and columns of the matrix, respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Portal Deletion Correctly

One critical pitfall is forgetting to delete the portal from the dictionary after using it for teleportation. If you don't remove the portal letter from teleport_positions after using it, the algorithm might repeatedly attempt to teleport using the same portal, leading to infinite loops or incorrect results.

Incorrect approach:

# Missing deletion - portal can be used infinitely
if current_cell in teleport_positions:
    for teleport_row, teleport_col in teleport_positions[current_cell]:
        if current_distance < distance[teleport_row][teleport_col]:
            distance[teleport_row][teleport_col] = current_distance
            queue.appendleft((teleport_row, teleport_col))
    # Forgot to delete: del teleport_positions[current_cell]

Solution: Always delete the portal letter from the dictionary immediately after processing all teleportation destinations to ensure it's only used once.

2. Incorrect Queue Order for 0-1 BFS

Another common mistake is adding both teleportation moves (cost 0) and regular moves (cost 1) to the same end of the deque. This breaks the 0-1 BFS property where cells with lower costs should be processed first.

Incorrect approach:

# Wrong - both moves added to the same end
queue.append((teleport_row, teleport_col))  # Should be appendleft for cost 0
queue.append((next_row, next_col))  # Correct for cost 1

Solution: Use appendleft() for teleportation moves (cost 0) and append() for regular moves (cost 1) to maintain proper processing order.

3. Processing Portals Multiple Times from Different Paths

If you check whether a portal has been used based on the current cell only, you might process the same portal multiple times when reaching it from different paths. This happens when multiple cells with the same letter are reached at different times.

Incorrect approach:

# Checking if current position was visited instead of checking portal availability
visited_portals = set()
if current_cell.isalpha() and (current_row, current_col) not in visited_portals:
    # This doesn't prevent using the same portal letter from different positions
    visited_portals.add((current_row, current_col))

Solution: Track portal usage by letter (not position) and delete the entire portal group from the dictionary after first use, ensuring the portal letter can only be used once globally.

4. Misunderstanding Portal Mechanics

A subtle pitfall is misunderstanding that stepping on a portal doesn't automatically trigger teleportation - it's optional. Also, you can walk through a portal cell normally without teleporting.

Incorrect approach:

# Forcing teleportation and not allowing normal movement through portal cells
if current_cell.isalpha():
    # Only process teleportation, skip normal adjacent moves
    for teleport_row, teleport_col in teleport_positions[current_cell]:
        # ...
    continue  # Wrong - should also check adjacent cells

Solution: Process both teleportation options AND normal adjacent cell movements when on a portal cell. The algorithm should explore all possibilities to find the optimal path.