3837. Grid Teleportation Traversal¶

Difficulty: Medium

3837. Grid Teleportation Traversal

Medium

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 i^th row and j^th 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:

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:

Constraints:

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

Solution¶

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Objects;
import java.util.PriorityQueue;

class Solution {
    private HashMap<Character, ArrayList<Pair >> map;
    static class State {
        int row, col, move;
        int freq[];
        public State(int row, int col, int move, int[] freq) {
            this.row = row;
            this.col = col;
            this.move = move;
            this.freq = freq;
        }
    }
    static class customSort implements Comparator<State> {
        @Override
        public int compare(State first, State second) {
            return Integer.compare(first.move, second.move);
        }
    }
    static class Pair {
        int row, col;
        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
        @Override
        public String toString() {
            return "(" + row + ", " + col + ")";
        }
        @Override
        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.row == row && p.col == col;
            }
            return false;
        }
        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }
    public int minMoves(String[] matrix) {
        int n = matrix.length, m = matrix[0].length();
        map = new HashMap<>();
        char arr[][] = new char[n][matrix[0].length()];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < matrix[i].length(); j++) {
                arr[i][j] = matrix[i].charAt(j);
                if (!map.containsKey(arr[i][j]))
                    map.put(arr[i][j], new ArrayList<>());
                map.get(arr[i][j]).add(new Pair(i, j));
            }
        }

        PriorityQueue<State> pq = new PriorityQueue<>(new customSort());
        pq.offer(new State(0, 0, 0, new int[26]));
        int dist[][] = new int[n][m];
        for (int current[] : dist)
            Arrays.fill(current, (int)(1e9));
        dist[0][0] = 0;
        int dir[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (pq.size() > 0) {
            int currRow = pq.peek().row, currCol = pq.peek().col, currMove = pq.peek().move;
            int currFreq[] = pq.peek().freq;
            pq.poll();

            if (arr[currRow][currCol] != '.') {
                if (currFreq[arr[currRow][currCol] - 'A'] == 0) {
                    int newFreq[] = new int[26];
                    newFreq = currFreq;
                    newFreq[arr[currRow][currCol] - 'A'] = 1;
                    ArrayList<Pair> cells = new ArrayList<>();
                    cells = map.get(arr[currRow][currCol]);
                    for (Pair x : cells) {
                        if (dist[x.row][x.col] > currMove) {
                            dist[x.row][x.col] = currMove;
                            pq.offer(new State(x.row, x.col, currMove, newFreq));
                        }
                    }
                }
            }

            for (int dire[] : dir) {
                int newRow = currRow + dire[0], newCol = currCol + dire[1];
                if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m || arr[newRow][newCol] == '#')
                    continue;
                if (dist[newRow][newCol] > currMove + 1) {
                    dist[newRow][newCol] = currMove + 1;
                    pq.offer(new State(newRow, newCol, currMove + 1, currFreq));
                }
            }
        }
        if (dist[n - 1][m - 1] == (int)(1e9))
            return -1;
        return dist[n - 1][m - 1];
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here