There is a ball in a maze
with empty spaces (represented as 0
) and walls (represented as 1
). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n
maze
, the ball's start
position and the destination
, where start = [startrow, startcol]
and destination = [destinationrow, destinationcol]
, return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination
, return -1
.
The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: 12 Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] Output: -1 Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1] Output: -1
Constraints:
m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j]
is0
or1
.start.length == 2
destination.length == 2
0 <= startrow, destinationrow < m
0 <= startcol, destinationcol < n
- Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
- The maze contains at least 2 empty spaces.
Companies: Google, ByteDance, Microsoft
Related Topics:
Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path
Similar Questions:
We BFS the matrix step by step. Each state is (x, y, direction)
and we visit them at most once.
The time complexity is O(4MN) = O(MN)
because each state (x, y, direction)
is visited at most once.
// OJ: https://leetcode.com/problems/the-maze-ii/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int shortestDistance(vector<vector<int>>& A, vector<int>& S, vector<int>& E) {
int M = A.size(), N = A[0].size(), step = 0, dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
vector<vector<vector<bool>>> seen(M, vector<vector<bool>>(N, vector<bool>(4))); // (x, y, direction)
queue<array<int, 3>> q;
for (int i = 0; i < 4; ++i) {
seen[S[0]][S[1]][i] = true;
q.push({S[0], S[1], i});
}
while (q.size()) {
int cnt = q.size();
while (cnt--) {
auto [x, y, dir] = q.front();
q.pop();
auto &[dx, dy] = dirs[dir];
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= M || ny < 0 || ny >= N || A[nx][ny]) { // The ball hits a wall. We can probe 4 directions
if (x == E[0] && y == E[1]) return step; // we can only check (x, y) if we are by a wall
for (int d = 0; d < 4; ++d) {
if (d == dir) continue;
auto &[dx, dy] = dirs[d];
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= M || ny < 0 || ny >= N || A[nx][ny] || seen[nx][ny][d]) continue;
seen[nx][ny][d] = true;
q.push({nx, ny, d});
}
} else if (!seen[nx][ny][dir]) { // The ball doesn't hit a wall. We can only move in the same direction.
seen[nx][ny][dir] = true;
q.push({nx, ny, dir});
}
}
++step;
}
return -1;
}
};
Solution 1 has lots of intermediate states that are not valid because the ball is still rolling. Here we can only keep track of those valid states, and log their distance.
We need to use a min heap to prioritize the states with shorter distance. This is in fact a Dijkstra algorithm.
Note that we might visit the same cell multiple times, we should only push the state into the heap if the distance is shorter.
Time complexity:
In the worst case we visit each node (O(MN)
), and for each node we probe 4 directions taking O(max(M, N))
time, and pushing into / popping from the heap takes O(log(MN))
time (assuming there are at most O(MN)
elements in the heap). So, the overall time complexity is O(MN * max(M, N) * log(MN))
.
But this is a loose upper bound because the more nodes visitable, the less steps we do during 4-directional probing.
This is more efficient than Solution 1 because we prioritize shorter distance and thus reach the end point earlier.
// OJ: https://leetcode.com/problems/the-maze-ii/
// Author: github.com/lzl124631x
// Time: O(MN * max(M, N) * log(MN))
// Space: O(MN)
class Solution {
public:
int shortestDistance(vector<vector<int>>& A, vector<int>& start, vector<int>& dest) {
int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
vector<vector<int>> dist(M, vector<int>(N, INT_MAX));
dist[start[0]][start[1]] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq; // min heap of (distance, x, y)
pq.push({0, start[0], start[1]});
while (pq.size()) {
auto [cost, x, y] = pq.top();
pq.pop();
if (cost > dist[x][y]) continue; // this state is no longer optimial, skip
if (x == dest[0] && y == dest[1]) return cost;
for (auto &[dx, dy] : dirs) { // probe 4 directions
int a = x, b = y, step = 0;
while (a >= 0 && a < M && b >= 0 && b < N && A[a][b] == 0) a += dx, b += dy, ++step;
a -= dx, b -= dy, --step; // once hit wall, step back
if (dist[a][b] > cost + step) {
dist[a][b] = cost + step;
pq.push({ dist[a][b], a, b });
}
}
}
return -1;
}
};