0% completed
Problem Statement
There is a ball in a maze with empty spaces (0)
and walls (1)
. The ball can move up
, down
, left
, or right
through empty spaces but won't stop until it hits a wall. When the ball stops, it can change direction.
Given an m x n
maze, the ball's start
position, and the destination
, where start = [start<sub>row</sub>, start<sub>col</sub>] and destination = [destination<sub>row</sub>, destination<sub>col</sub>], find the shortest distance for the ball to reach the destination. If the ball can't reach the destination, return -1.
The distance is the number of empty spaces traveled by the ball from the start (excluded) to the destination (included).
Examples
Example 1
- Input: start = [0, 1], destination = [4, 4], 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]]
- Expected Output:
7
- Justification: The ball travels from the start
(0,1)
down to(2,1)
, right to(2, 2)
, down to(4, 2)
, and right to (4, 4) in 7 moves.
Example 2
- Input: start = [0, 0], destination = [4, 4], maze =
[[0, 0, 0, 0, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0]]
- Expected Output:
8
- Justification: The ball travels from (0,0) right to (0,4), down to (4,4) in 8 moves.
Example 3
- Input: start = [0, 1], destination = [3, 1], maze =
[[0, 0, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 1], [1, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
- Expected Output:
-1
- Justification: The ball cannot reach the destination (3,1) due to walls blocking the path.
Constraints:
- m == maze.length
- n == maze[i].length
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1.
- start.length == 2
- destination.length == 2
- 0 <= start<sub>row</sub>, destination<sub>row</sub> < m
- 0 <= start<sub>col</sub>, destination<sub>col</sub> < 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.
Try it yourself
Try solving this question here:
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible