Show problems as
Classic problem #490MediumArrayDepth-First SearchBreadth-First SearchMatrix

The Maze

Real-world version: Rolling a Bearing Through the Trays
Tracked in this browser only
Read The Maze on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tray is given as maze, where 0 is open and 1 is a wall. A bearing starts at the cell start, given as [row, column].

A roll sends the bearing in one of the four directions along the rows or columns; it keeps going until it is stopped by a wall or by the edge of the tray, and only then may another roll be chosen. The bearing cannot be stopped part way.

Return true when some sequence of rolls leaves the bearing resting on destination, given the same way.

Examples

Example 1

Input
maze = [[0, 0, 0]], start = [0, 0], destination = [0, 1]
Output
false

A roll along the row cannot stop in the middle, so the bearing goes straight past the destination to the far end.

Example 2

Input
maze = [[0, 0, 0]], start = [0, 0], destination = [0, 2]
Output
true

Rolling right carries the bearing to the far end of the row, which is where the destination sits.

Example 3

Input
maze = [[0, 1, 0]], start = [0, 0], destination = [0, 2]
Output
false

A wall sits between the two cells, so the bearing cannot get past it at all.

Constraints

  • 1 <= maze.length <= 100
  • 1 <= maze[i].length <= 100
  • Every row of maze has the same length
  • maze[i][j] is 0 or 1
  • start.length == 2
  • destination.length == 2
  • 0 <= start[0] < maze.length
  • 0 <= start[1] < maze[i].length
  • 0 <= destination[0] < maze.length
  • 0 <= destination[1] < maze[i].length
  • Both the start and the destination are open cells, and they are not the same cell

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def has_path(maze: list[list[int]], start: list[int], destination: list[int]) -> bool:
Java
public boolean hasPath(int[][] maze, int[] start, int[] destination)

More on the same topics