JavaMedium

Fewest hops across a grid of racks

A data-centre floor is a grid. Each cell is open ('.') or a rack ('#'). A technician starts at the top-left cell and must reach the bottom-right, moving up, down, left or right, never diagonally, never through a rack.

Return the number of moves on a shortest route, or -1 if there is none. The start and the goal are always open cells; a one-by-one grid needs zero moves.

Every move costs the same, which is the whole reason this is breadth-first search and not Dijkstra: the first time BFS reaches the goal, it has found a shortest route.

Example

inputgrid = ["..#", ".#.", "..."]output4

Down, down, right, right: four moves. The direct diagonal is blocked by the rack in the middle.

Constraints

1 ≤ rows, cols ≤ 1,000
grid[0][0] and grid[rows-1][cols-1] are '.'

Hints

Hint 1

A queue of cells and a visited set — or mark visited cells in a copy of the grid. Push the start with distance 0.

Hint 2

Mark a cell visited when you ENQUEUE it, not when you dequeue it, or a cell can be queued many times and the queue grows past the grid.

Hint 3

The lesson's visited set is not optional: without it the walk revisits cells forever.

Stuck? The lesson behind this problem: 🧮 Breadth-first and depth-first

java

Tab indents · Escape first to tab out

Test cases

These are the specification. Run tests checks your answer against them.

Case	Input	Expected
the example	`["..#", ".#.", "..."]`	`4`
one cell	`["."]`	`0`
walled off	`[".#", "#."]`	`-1`
a corridor	`["....", "###.", "...."]`	`5`
an open thousand by thousand	`1000 rows of 1000 dots`	`1998`