Steps to the Nearest Snack

Medium

An office is given as a rectangular grid of characters grid: - * is you (there is exactly one such cell); - # is a cell with a snack (there may be any number of them, including none); - O is an open walkway; - X is a wall you cannot pass. In one step you can move to a cell that shares a side with yours, as long as it is not a wall. Return the fewest steps needed to reach any snack cell, or -1 if none can be reached.

Example 1

grid=[["*", "O", "X", "#"], ["O", "O", "O", "O"], ["X", "#", "X", "O"]] → 3

To the snack at the bottom: down to (1, 0), right to (1, 1), down to (2, 1), 3 steps. The snack at the top right would take 5.

Example 2

grid=[["O", "X", "#"], ["*", "X", "O"]] → -1

A column of walls cuts the snack off, so the answer is -1.

Constraints

m == len(grid), n == len(grid[i])
1 ≤ m, n ≤ 200
grid[i][j] is one of *, X, O, #
* appears exactly once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Steps to the Nearest Exit Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium

Input

grid=[["*", "O", "X", "#"], ["O", "O", "O", "O"], ["X", "#", "X", "O"]]

Expected

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