Can the Ball Stop at the Target

Medium

A maze is given by an m × n grid grid: 0 is an open cell and 1 is a wall. Everything outside the grid counts as a wall too. A ball rests on cell start = [row, col]. You can push it up, down, left or right, and it rolls through open cells until it bumps into a wall. Only once it has stopped can you push it again, in any direction. Return true if the ball can be brought to rest exactly on cell target = [row, col], and false otherwise. Rolling through target without stopping does not count.

Example 1

grid=[[0, 0, 0], [1, 1, 0], [0, 0, 0]], start=[0, 0], target=[2, 0] → True

Push right and the ball stops at [0, 2], push down and it stops at [2, 2], push left and it stops at [2, 0].

Example 2

grid=[[0, 0, 0], [0, 0, 0], [0, 0, 0]], start=[0, 0], target=[1, 1] → False

There are no inner walls, so the ball always rolls all the way to an edge. It can pass through the centre but never stop there.

Constraints

1 ≤ m, n ≤ 100
grid[i][j] is 0 or 1
start and target are distinct open cells inside the grid

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Rain Reaching Both Seas Medium Shortest Path of a Rolling Ball Medium Open a Minefield Cell Medium

Input

grid=[[0, 0, 0], [1, 1, 0], [0, 0, 0]], start=[0, 0], target=[2, 0]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.