Ball Into the Hole

Hard

A field is given by the matrix field: 0 is an empty cell and 1 is a wall. The edges of the field act as walls too. A ball sits in cell start and there is a hole in cell hole. The ball can be pushed up (u), down (d), left (l) or right (r). It keeps rolling that way until it hits a wall or the edge of the field, and it can only be pushed again once it stops. If the ball rolls over the hole, it drops into it. The length of a route is the number of cells the ball rolls through (the start cell does not count, the hole does). Return a string of the letters u, d, l, r: the sequence of pushes that gets the ball into the hole along the shortest route. If several routes are equally short, return the alphabetically smallest string. If the ball cannot reach the hole, return "impossible".

Example 1

field=[[0, 0, 0], [0, 1, 0], [0, 0, 0]], start=[0, 0], hole=[2, 2] → 'dr'

There are two routes of length 4: down then right (dr) and right then down (rd). The alphabetically smaller one, dr, is chosen.

Example 2

field=[[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0]], start=[0, 0], hole=[0, 2] → 'r'

Rolling right, the ball passes over the hole and drops into it after 2 cells.

Example 3

field=[[0, 1, 0], [0, 1, 0]], start=[0, 0], hole=[1, 2] → 'impossible'

The wall in the middle separates the left column from the right one, so the hole cannot be reached.

Constraints

1 ≤ m, n ≤ 100, where m and n are the numbers of rows and columns of field
field[i][j] is 0 or 1
start and hole are [row, column] coordinates of empty cells inside the field
start and hole are different

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Array String Matrix Shortest Path Heap (Priority Queue)