# Grid Teleportation Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/grid-teleportation-traversal)
Canonical: https://scaleengineer.com/dsa/problems/grid-teleportation-traversal
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table, Matrix
---
## Problem
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`.

**Example 1:**

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

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/grid-teleportation-traversal/image0.png)

* Before the first move, teleport from `(0, 0)` to `(1, 1)`.
* In the first move, move from `(1, 1)` to `(1, 2)`.
* In the second move, move from `(1, 2)` to `(2, 2)`.

**Example 2:**

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

**Output:** 13

**Explanation:**

![](https://assets.glich.co/dsa/grid-teleportation-traversal/image1.gif)

**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.

# Approaches
## 0-1 BFS on Augmented State Space
This approach models the problem as a shortest path search on a very large state graph. A state is defined not just by the current position `(row, col)` but also by the set of portals that have been used, represented by a bitmask. Since moves can have a cost of 1 (standard move) or 0 (teleportation), this is a classic 0-1 shortest path problem, which can be solved efficiently using a 0-1 Breadth-First Search (BFS) with a deque.
**Time:** O(m * n * 2^K). Each state is visited at most once. From each state, we explore a constant number of neighbors and potentially a set of teleport destinations. · **Space:** O(m * n * 2^K), where `m` and `n` are grid dimensions and `K` is the number of unique portal types. This is prohibitively large.
**Pros:** Conceptually simple as it's a direct extension of BFS for shortest paths.; Guaranteed to find the optimal solution if it runs to completion.
**Cons:** Extremely high time and space complexity, making it infeasible for the given constraints.; The memory required for the `dist` array (`m * n * 2^K`) would exceed typical limits for `K > 15`.; Likely to result in Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) on most platforms.
### Explanation
The core idea is to augment the standard grid BFS state `(row, col)` with a bitmask `mask` to keep track of used portals. The state `(row, col, mask)` represents being at cell `(r, c)` having used the portals indicated by `mask`.

We use a distance array `dist[m][n][1 << K]` (where `K` is the number of portal types, up to 26) to store the minimum moves to reach each state. The search proceeds as follows:

1.  **Initialization**: Pre-process the grid to map portal letters to indices and find their locations. Initialize `dist` with infinity. Set `dist[0][0][0] = 0` and push `(0, 0, 0)` to a deque. A special check is needed if `(0,0)` is a portal to handle immediate teleportation.
2.  **0-1 BFS Loop**: While the deque is not empty, extract the state `(r, c, mask)` with distance `d` from the front.
3.  **Regular Moves (Cost 1)**: For each valid neighbor `(nr, nc)`, if `d + 1 < dist[nr][nc][mask]`, update the distance and push `(nr, nc, mask)` to the *back* of the deque.
4.  **Teleportation (Cost 0)**: If `matrix[r][c]` is an unused portal `L` (checked via `mask`), calculate `new_mask = mask | (1 << L)`. For every other cell `(tr, tc)` with portal `L`, if `d < dist[tr][tc][new_mask]`, update its distance and push `(tr, tc, new_mask)` to the *front* of the deque.

The final answer is `min(dist[m-1][n-1][mask])` over all `mask`. While conceptually simple, this approach is not practical due to its massive state space.
### Algorithm
- The state of the search is defined by `(row, col, mask)`, where `(row, col)` is the current cell and `mask` is a bitmask representing the set of portals used.
- A distance array `dist[row][col][mask]` is used to store the minimum moves to reach each state, initialized to infinity.
- A double-ended queue (deque) is used to perform a 0-1 Breadth-First Search (BFS).
- The search starts by initializing `dist[0][0][0] = 0` and adding the state `(0, 0, 0)` to the deque.
- The algorithm iteratively processes states from the deque:
  - When moving to an adjacent cell, the cost increases by 1, and the new state is added to the back of the deque.
  - When teleporting, the cost is 0, the mask is updated, and the new state(s) are added to the front of the deque.
- The final answer is the minimum distance found in `dist[m-1][n-1][mask]` across all possible masks.

## BFS Precomputation with DP on Portal Subsets
This highly efficient approach separates the problem into two distinct parts: grid traversal and combinatorial path selection. First, it precomputes all relevant shortest path distances within the grid using a series of Breadth-First Searches (BFS). These distances include start-to-cell, cell-to-end, and portal-to-cell. Second, it uses these precomputed costs to build a small, abstract graph where nodes are the start, end, and portal types. The final step is to find the shortest path in this new graph, respecting the 'use each portal once' constraint. This is a classic Traveling Salesperson Problem (TSP) variant on a small number of nodes, solvable with Dynamic Programming on subsets.
**Time:** O(K * m * n + 2^K * K^2). `O(K*m*n)` for the BFS precomputation phase, and `O(2^K * K^2)` for the Dijkstra's algorithm on the portal states. · **Space:** O(K * m * n + 2^K * K). The `O(K*m*n)` term dominates for storing precomputed distances, and `O(2^K*K)` for the DP table.
**Pros:** Highly efficient and tailored for the problem's constraints.; Handles cases with large grids but few portals, and cases with many portals but small grids effectively.; Guaranteed to find the optimal solution.
**Cons:** Significantly more complex to implement compared to a simple BFS.; The precomputation phase can be time and memory-intensive if both `K` and the grid size are large (`O(K*m*n)` space).
### Explanation
This method is a hybrid approach that tackles the geometric and combinatorial complexities separately, making it feasible for the given constraints.

### Phase 1: Precomputation using BFS
We run `K+2` separate BFS traversals on the grid to find all necessary distances:
1.  **`dist_from_start`**: A single-source BFS from `(0,0)` to find the shortest moves to every other cell.
2.  **`dist_to_end`**: A single-source BFS from `(m-1,n-1)` to find the shortest moves from every cell to the destination.
3.  **`dist_from_portals`**: For each of the `K` portal types, we run a multi-source BFS. The queue is initialized with all cells of a given portal type at distance 0. This gives us the shortest distance from that portal type to every other cell in the grid.

### Phase 2: Building the Portal Graph
With the distances from Phase 1, we can define the edge weights in an abstract graph of portals:
-   `cost_start_p[i]`: The cost to travel from `(0,0)` to the nearest cell of portal `i`.
-   `cost_p_end[i]`: The cost to travel from the nearest cell of portal `i` to `(m-1,n-1)`.
-   `cost_p_p[i][j]`: The cost to travel from any cell of portal `i` to the nearest cell of portal `j`.

### Phase 3: DP on Subsets (via Dijkstra)
The problem reduces to finding a simple path (no repeated portal nodes) in this abstract graph. We use Dijkstra's algorithm on the state `(cost, mask, last_portal)`:
-   `dp[mask][last_portal]` stores the minimum cost of a path from `start` that visits the portals in `mask` and ends at `last_portal`.
-   The priority queue is initialized with paths from `start` to each portal `i`.
-   Dijkstra explores paths by adding one unvisited portal at a time, using the `cost_p_p` matrix for edge weights.

### Phase 4: Calculating the Final Answer
The overall minimum moves is the minimum of two values:
1.  The direct path cost: `dist_from_start[m-1][n-1]`.
2.  The minimum cost over all portal paths: `min(dp[mask][i] + cost_p_end[i])` for all `i` and `mask`.

```java
import java.util.*;

class Solution {
    private static final int INF = Integer.MAX_VALUE / 2;

    public int minimumMoves(String[] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        Map<Character, List<int[]>> portalLocations = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = matrix[i].charAt(j);
                if (Character.isUpperCase(c)) {
                    portalLocations.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[]{i, j});
                }
            }
        }

        List<Character> portalChars = new ArrayList<>(portalLocations.keySet());
        int k = portalChars.size();
        Map<Character, Integer> portalIndexMap = new HashMap<>();
        for (int i = 0; i < k; i++) {
            portalIndexMap.put(portalChars.get(i), i);
        }

        int[][] distFromStart = bfs(new int[]{0, 0}, m, n, matrix);
        int[][] distToEnd = bfs(new int[]{m - 1, n - 1}, m, n, matrix);

        int[][] distFromPortals = new int[k][m * n];
        for (int i = 0; i < k; i++) {
            char pChar = portalChars.get(i);
            List<int[]> sources = portalLocations.get(pChar);
            int[][] tempDist = bfs(sources.toArray(new int[0][]), m, n, matrix);
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    distFromPortals[i][r * n + c] = tempDist[r][c];
                }
            }
        }

        int[] costStartToPortal = new int[k];
        Arrays.fill(costStartToPortal, INF);
        for (int i = 0; i < k; i++) {
            for (int[] pos : portalLocations.get(portalChars.get(i))) {
                costStartToPortal[i] = Math.min(costStartToPortal[i], distFromStart[pos[0]][pos[1]]);
            }
        }

        int[] costPortalToEnd = new int[k];
        Arrays.fill(costPortalToEnd, INF);
        for (int i = 0; i < k; i++) {
            for (int[] pos : portalLocations.get(portalChars.get(i))) {
                costPortalToEnd[i] = Math.min(costPortalToEnd[i], distToEnd[pos[0]][pos[1]]);
            }
        }

        int[][] costPortalToPortal = new int[k][k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (i == j) continue;
                int minCost = INF;
                for (int[] pos : portalLocations.get(portalChars.get(j))) {
                    minCost = Math.min(minCost, distFromPortals[i][pos[0] * n + pos[1]]);
                }
                costPortalToPortal[i][j] = minCost;
            }
        }

        int[][] dp = new int[1 << k][k];
        for (int[] row : dp) Arrays.fill(row, INF);

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        for (int i = 0; i < k; i++) {
            if (costStartToPortal[i] != INF) {
                dp[1 << i][i] = costStartToPortal[i];
                pq.offer(new int[]{dp[1 << i][i], 1 << i, i});
            }
        }

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int cost = curr[0];
            int mask = curr[1];
            int u = curr[2];

            if (cost > dp[mask][u]) continue;

            for (int v = 0; v < k; v++) {
                if ((mask & (1 << v)) == 0) { // if v is not visited
                    int newCost = cost + costPortalToPortal[u][v];
                    if (newCost < dp[mask | (1 << v)][v]) {
                        dp[mask | (1 << v)][v] = newCost;
                        pq.offer(new int[]{newCost, mask | (1 << v), v});
                    }
                }
            }
        }

        int minMoves = distFromStart[m - 1][n - 1];

        for (int mask = 0; mask < (1 << k); mask++) {
            for (int i = 0; i < k; i++) {
                if (dp[mask][i] != INF && costPortalToEnd[i] != INF) {
                    minMoves = Math.min(minMoves, dp[mask][i] + costPortalToEnd[i]);
                }
            }
        }

        return minMoves == INF ? -1 : minMoves;
    }

    private int[][] bfs(int[][] sources, int m, int n, String[] matrix) {
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, INF);
        Queue<int[]> q = new LinkedList<>();

        for (int[] src : sources) {
            dist[src[0]][src[1]] = 0;
            q.offer(src);
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr].charAt(nc) != '#' && dist[nr][nc] == INF) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return dist;
    }

    private int[][] bfs(int[] source, int m, int n, String[] matrix) {
        return bfs(new int[][]{source}, m, n, matrix);
    }
}
```
### Algorithm
- **Phase 1: Precomputation with BFS**
  - Identify all `K` portal types and their locations.
  - Run a BFS from `(0,0)` to find `dist_from_start[r][c]`.
  - Run a BFS from `(m-1,n-1)` to find `dist_to_end[r][c]`.
  - For each of the `K` portal types, run a multi-source BFS starting from all its cells to find `dist_from_portal[i][r][c]`.
- **Phase 2: Portal Graph Cost Calculation**
  - Use the precomputed distances to find the costs between `start`, `end`, and all portal types.
  - `cost_start_p[i]`: min cost from `start` to any cell of portal `i`.
  - `cost_p_end[i]`: min cost from any cell of portal `i` to `end`.
  - `cost_p_p[i][j]`: min cost from any cell of portal `i` to any cell of portal `j`.
- **Phase 3: DP on Subsets**
  - Solve the shortest simple path problem on the portal graph using Dijkstra's algorithm on an augmented state `(cost, mask, last_portal)`.
  - A DP table `dp[mask][i]` stores the minimum cost to visit portals in `mask`, ending at portal `i`.
- **Phase 4: Final Answer**
  - The result is the minimum of the direct path (`dist_from_start[m-1][n-1]`) and all paths going through portals (`dp[mask][i] + cost_p_end[i]`).

# Solutions
### Java

```java
class Solution {
public
  int minMoves(String[] matrix) {
    int m = matrix.length, n = matrix[0].length();
    Map<Character, List<int[]>> g = new HashMap<>();
    for (int i = 0; i < m; i++) {
      String row = matrix[i];
      for (int j = 0; j < n; j++) {
        char c = row.charAt(j);
        if (Character.isAlphabetic(c)) {
          g.computeIfAbsent(c, k->new ArrayList<>()).add(new int[]{i, j});
        }
      }
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    int INF = Integer.MAX_VALUE / 2;
    int[][] dist = new int[m][n];
    for (int[] arr : dist)
      Arrays.fill(arr, INF);
    dist[0][0] = 0;
    Deque<int[]> q = new ArrayDeque<>();
    q.add(new int[]{0, 0});
    while (!q.isEmpty()) {
      int[] cur = q.pollFirst();
      int i = cur[0], j = cur[1];
      int d = dist[i][j];
      if (i == m - 1 && j == n - 1)
        return d;
      char c = matrix[i].charAt(j);
      if (g.containsKey(c)) {
        for (int[] pos : g.get(c)) {
          int x = pos[0], y = pos[1];
          if (d < dist[x][y]) {
            dist[x][y] = d;
            q.addFirst(new int[]{x, y});
          }
        }
        g.remove(c);
      }
      for (int idx = 0; idx < 4; idx++) {
        int a = dirs[idx], b = dirs[idx + 1];
        int x = i + a, y = j + b;
        if (0 <= x && x < m && 0 <= y && y < n && matrix[x].charAt(y) != '#' &&
            d + 1 < dist[x][y]) {
          dist[x][y] = d + 1;
          q.addLast(new int[]{x, y});
        }
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMoves(vector<string> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    unordered_map<char, vector<pair<int, int>>> g;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        char c = matrix[i][j];
        if (isalpha(c))
          g[c].push_back({i, j});
      }
    int dirs[5] = {-1, 0, 1, 0, -1};
    int INF = numeric_limits<int>::max() / 2;
    vector<vector<int>> dist(m, vector<int>(n, INF));
    dist[0][0] = 0;
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    while (!q.empty()) {
      auto [i, j] = q.front();
      q.pop_front();
      int d = dist[i][j];
      if (i == m - 1 && j == n - 1)
        return d;
      char c = matrix[i][j];
      if (g.count(c)) {
        for (auto [x, y] : g[c])
          if (d < dist[x][y]) {
            dist[x][y] = d;
            q.push_front({x, y});
          }
        g.erase(c);
      }
      for (int idx = 0; idx < 4; ++idx) {
        int x = i + dirs[idx], y = j + dirs[idx + 1];
        if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] != '#' &&
            d + 1 < dist[x][y]) {
          dist[x][y] = d + 1;
          q.push_back({x, y});
        }
      }
    }
    return -1;
  }
};

```

### Python

```python
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

```