0957MediumArrayDepth-First SearchBreadth-First SearchMatrix

Rolling a Bearing Through the Trays

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(m * n * (m + n)) for an m by n tray: each resting place tries four slides.Space O(m * n) for the seen marks and the queue.

The bearing only ever comes to rest where something stops it, so the cells worth thinking about are the resting places, and a roll takes one resting place to another. That makes the tray a graph over resting places, and the question is whether the destination can be reached in it. So sweep outwards from the start: for each resting place, try all four directions, slide as far as the walls allow to find where that roll ends, and take up any resting place not seen before. Marking resting places as seen keeps the sweep finite, and reaching the destination as a resting place answers yes. Note that rolling past the destination without stopping there does not count.

Pythonentry point: has_path

def has_path(maze, start, destination):
    from collections import deque
    m = len(maze)
    n = len(maze[0])
    target = (destination[0], destination[1])
    seen = [[False] * n for _ in range(m)]
    seen[start[0]][start[1]] = True
    queue = deque([(start[0], start[1])])
    while queue:
        r, c = queue.popleft()
        if (r, c) == target:
            return True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r
            nc = c
            while True:
                tr = nr + dr
                tc = nc + dc
                if tr < 0 or tc < 0 or tr >= m or tc >= n or maze[tr][tc] == 1:
                    break
                nr = tr
                nc = tc
            if not seen[nr][nc]:
                seen[nr][nc] = True
                queue.append((nr, nc))
    return False

The obvious version

Walk out every sequence of rolls, keeping the resting places already visited on the current line of play so it cannot go round for ever, and report success if any line reaches the destination. Explores the sequences rather than treating the resting places as a graph.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_has_path(maze, start, destination):
    m = len(maze)
    n = len(maze[0])
    target = (destination[0], destination[1])
    found = [False]
    seen = set()

    def roll(r, c):
        if found[0]:
            return
        if (r, c) == target:
            found[0] = True
            return
        seen.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r
            nc = c
            while True:
                tr = nr + dr
                tc = nc + dc
                if tr < 0 or tc < 0 or tr >= m or tc >= n or maze[tr][tc] == 1:
                    break
                nr = tr
                nc = tc
            if (nr, nc) not in seen:
                roll(nr, nc)

    roll(start[0], start[1])
    return found[0]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in