In this guide, you will get 3552. Grid Teleportation Traversal LeetCode Solution with the best time and space complexity. The solution to Grid Teleportation Traversal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(mn\log mn)
Space Complexity: O(mn)
3552. Grid Teleportation Traversal LeetCode Solution in C++
class Solution {
public:
// Similar to 3341. Find Minimum Time to Reach Last Room I
int minMoves(vector<string>& matrix) {
if (matrix.back().back() == '#')
return -1;
vector<vector<pair<int, int>>> teleportPositions(26);
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (matrix[i][j] != '.' && matrix[i][j] != '#')
teleportPositions[matrix[i][j] - 'A'].emplace_back(i, j);
return dijkstra(matrix, teleportPositions, {0, 0},
{matrix.size() - 1, matrix[0].size() - 1});
}
private:
int dijkstra(const vector<string>& matrix,
const vector<vector<pair<int, int>>>& teleportPositions,
const pair<int, int>& src, const pair<int, int>& dst) {
constexpr int kDirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = matrix.size();
const int n = matrix[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
vector<bool> seen(26);
dist[0][0] = 0;
using T = pair<int, pair<int, int>>; // (d, u)
priority_queue<T, vector<T>, greater<>> minHeap;
minHeap.push({dist[0][0], src});
while (!minHeap.empty()) {
const auto [d, u] = minHeap.top();
minHeap.pop();
if (u == dst)
return d;
const auto [i, j] = u;
if (d > dist[i][j])
continue;
const char c = matrix[i][j];
if (isupper(c) && !seen[c - 'A']) {
seen[c - 'A'] = true;
for (const auto& [x, y] : teleportPositions[c - 'A'])
if (d < dist[x][y]) {
dist[x][y] = d;
minHeap.push({d, {x, y}});
}
}
for (const auto& [dx, dy] : kDirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (matrix[x][y] == '#')
continue;
if (d + 1 < dist[x][y]) {
dist[x][y] = d + 1;
minHeap.push({d + 1, {x, y}});
}
}
}
return -1;
}
}; /* code provided by PROGIEZ */
3552. Grid Teleportation Traversal LeetCode Solution in Java
class Solution {
// Similar to 3341. Find Minimum Time to Reach Last Room I
public int minMoves(String[] matrix) {
if (matrix[matrix.length - 1].charAt(matrix[0].length() - 1) == '#')
return -1;
List<Pair<Integer, Integer>>[] teleportPositions = new ArrayList[26];
for (int i = 0; i < 26; ++i)
teleportPositions[i] = new ArrayList<>();
for (int i = 0; i < matrix.length; ++i)
for (int j = 0; j < matrix[0].length(); ++j) {
final char c = matrix[i].charAt(j);
if (c != '.' && c != '#')
teleportPositions[c - 'A'].add(new Pair<>(i, j));
}
return dijkstra(matrix, teleportPositions, new Pair<>(0, 0),
new Pair<>(matrix.length - 1, matrix[0].length() - 1));
}
private int dijkstra(String[] matrix, List<Pair<Integer, Integer>>[] teleportPositions,
Pair<Integer, Integer> src, Pair<Integer, Integer> dst) {
final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int m = matrix.length;
final int n = matrix[0].length();
int[][] dist = new int[m][n];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
boolean[] seen = new boolean[26];
dist[0][0] = 0;
Queue<Pair<Integer, Pair<Integer, Integer>>> minHeap =
new PriorityQueue<>(Comparator.comparingInt(Pair::getKey)) {
{ offer(new Pair<>(dist[0][0], src)); } // (d, u)
};
while (!minHeap.isEmpty()) {
final int d = minHeap.peek().getKey();
final Pair<Integer, Integer> u = minHeap.poll().getValue();
if (u.equals(dst))
return d;
final int i = u.getKey();
final int j = u.getValue();
if (d > dist[i][j])
continue;
final char c = matrix[i].charAt(j);
if (Character.isUpperCase(c) && !seen[c - 'A']) {
seen[c - 'A'] = true;
for (Pair<Integer, Integer> pos : teleportPositions[c - 'A']) {
final int x = pos.getKey();
final int y = pos.getValue();
if (d < dist[x][y]) {
dist[x][y] = d;
minHeap.offer(new Pair<>(d, new Pair<>(x, y)));
}
}
}
for (int[] dir : DIRS) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (matrix[x].charAt(y) == '#')
continue;
if (d + 1 < dist[x][y]) {
dist[x][y] = d + 1;
minHeap.offer(new Pair<>(d + 1, new Pair<>(x, y)));
}
}
}
return -1;
}
} // code provided by PROGIEZ
3552. Grid Teleportation Traversal LeetCode Solution in Python
class Solution:
# Similar to 3341. Find Minimum Time to Reach Last Room I
def minMoves(self, matrix: list[str]) -> int:
if matrix[-1][-1] == '#':
return -1
teleportPositions = [[] for _ in range(26)]
for i, row in enumerate(matrix):
for j, c in enumerate(row):
if c not in ('.', '#'):
teleportPositions[ord(c) - ord('A')].append((i, j))
return self._dijkstra(matrix, teleportPositions,
(0, 0), (len(matrix) - 1, len(matrix[0]) - 1))
def _dijkstra(
self,
matrix: list[str],
teleportPositions: list[list[tuple[int, int]]],
src: tuple[int, int],
dst: tuple[int, int],
) -> int:
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
m = len(matrix)
n = len(matrix[0])
dist = [[math.inf] * n for _ in range(m)]
seen = set()
dist[0][0] = 0
minHeap = [(dist[0][0], src)] # (d, u)
while minHeap:
d, u = heapq.heappop(minHeap)
if u == dst:
return d
i, j = u
if d > dist[i][j]:
continue
c = matrix[i][j]
if c.isupper() and c not in seen:
seen.add(c)
for x, y in teleportPositions[ord(c) - ord('A')]:
if d < dist[x][y]:
dist[x][y] = d
heapq.heappush(minHeap, (d, (x, y)))
for dx, dy in DIRS:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if matrix[x][y] == '#':
continue
if d + 1 < dist[x][y]:
dist[x][y] = d + 1
heapq.heappush(minHeap, (d + 1, (x, y)))
return -1 # code by PROGIEZ
