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 true
if the ball can stop at the destination, otherwise return false
.
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: true Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
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: false 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: false
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: Facebook, TikTok, Square
Related Topics:
Depth-First Search, Breadth-First Search, Graph
Similar Questions:
// OJ: https://leetcode.com/problems/the-maze/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
bool hasPath(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<bool>> seen(M, vector<bool>(N));
queue<pair<int, int>> q{{{start[0], start[1]}}};
seen[start[0]][start[1]] = true;
while (q.size()) {
auto [x, y] = q.front();
q.pop();
if (x == dest[0] && y == dest[1]) return true;
for (auto &[dx, dy] : dirs) {
int a = x, b = y;
while (a >= 0 && a < M && b >= 0 && b < N && A[a][b] != 1) a += dx, b += dy;
a -= dx, b -= dy;
if ((a == x && b == y) || seen[a][b]) continue;
seen[a][b] = true;
q.emplace(a, b);
}
}
return false;
}
};