Shortest Path in 8 Directions
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A cleaning robot crosses an room grid, where 0 is a free cell and 1 is blocked by furniture.
The robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (H-1, W-1). Each move goes to a free
neighbouring cell in any of the 8 directions (including diagonals); a diagonal move is allowed even if both side cells are blocked.
Return the minimum number of cells on the path, including the start and the end, or -1 if the end cannot be reached or
the start or end cell is blocked.
Examples
| grid | result |
|---|---|
[[0, 1], [1, 0]] | 2 |
[[0, 0, 0], [1, 1, 0], [1, 1, 0]] | 4 |
[[1, 0, 0], [1, 1, 0], [1, 1, 0]] | -1 |
Example 1 — One diagonal move: cells (0,0) and (1,1).
Example 2 — (0,0) → (0,1) → (1,2) → (2,2) visits 4 cells.
Example 3 — The start cell is blocked.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(grid: int[][]) → int
Constraints
-
grid.length -
grid[i].length; all rows have the same length. grid[i][j]is0or1.
Expected complexity
- Time
- O(HW)
- Space
- O(HW)
Examples
| grid | Expected |
|---|---|
[[0,1],[1,0]] | 2 |
[[0,0,0],[1,1,0],[1,1,0]] | 4 |
[[1,0,0],[1,1,0],[1,1,0]] | -1 |
Hint
Hint
Every move costs 1, so a BFS from (0, 0) over the 8 neighbour directions gives the answer. Return -1 immediately if the
start or end is blocked, and mark cells visited when you enqueue them. Re-sweeping the whole grid until no distance changes
needs as many sweeps as the path is long on a winding maze, which times out.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1114 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 5 | verdict only |