10505. The Maze II

A ball is placed in a rectangular maze consisting of open cells and walls. The ball can roll in four directions: up, down, left, or right. Once it starts rolling in a direction, it continues moving until it encounters a wall. When it stops, it can choose a new direction to roll.

Given the maze layout, the starting position of the ball, and a target position, determine the minimum number of empty cells the ball must pass through to reach and stop at the target. The distance is measured as the count of empty cells traversed from the starting cell (not included) to the target (included). If the ball can't stop at the destination, return -1.

The maze is represented by a string list where each row is a space separated list of integers, where 0 represents an open cell and 1 represents a wall. The start and target are specified as [row, col] pairs. The outer boundary of the maze is surrounded by walls.

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, 3]
end = [4, 4]

Output: 11

Explanation:
A shortest path is: down → down → right → right → down → left → down.
The total steps are 2 + 2 + 1 + 1 + 2 + 1 + 2 = 11.
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, 0]
end = [3, 2]

Output: -1

Explanation:
There is no way for the ball to stop at the destination.

Constraints

  • The maze contains at least 3 empty spaces.
  • The width and height of the maze are both between 2 and 120.
  • There is exactly one ball and one target in the maze.
  • The ball and the target are located in open cells, and are not initially at the same position.




Please use Laptop/Desktop or any other large screen to add/edit code.