Funcia
Lv.30-1-bfsgridshortest-path

Escape Breaking the Fewest Walls

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

In grid, 0 is open and 1 is a wall that can be broken. Moving in four directions from (0, 0) to the bottom-right cell, return the minimum number of walls to break. Both corners are open.

Examples

gridresult
[[0, 1, 1], [1, 1, 0], [1, 1, 0]]2
[[0, 0, 0], [1, 1, 0], [0, 0, 0]]0
[[0]]0

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

  • 1≤H,W≤5001 \le H, W \le 500; grid[i][j] is 0 or 1; both corners are 0

Expected complexity

Time
O(HW)
Space
O(HW)

Examples

gridExpected
[[0,1,1],[1,1,0],[1,1,0]]2
[[0,0,0],[1,1,0],[0,0,0]]0
[[0]]0

Hint

Hint

Shortest path with edge costs 0 (open cell) or 1 (wall): 0-1 BFS with a deque (push cost-0 moves to the front, cost-1 to the back), or Dijkstra with a heap. Array-scan Dijkstra is O((HW)2)O((HW)^2).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251074 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.