Funcia
Lv.2bfsgraphgrid

Mold Spread Time

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

A floor is a grid where 1 is moldy, 0 is clean and -1 is a wall. Every minute mold spreads to clean cells sharing an edge with a moldy cell. Return the minimum number of minutes until no clean cell remains, -1 if some clean cell is never reached, or 0 if there are no clean cells to begin with.

Examples

gridresult
[[1, 0, 0], [0, -1, 0], [0, 0, 0]]4
[[1, -1, 0], [0, -1, 0]]-1
[[1, 0, 1], [0, 0, 0]]2

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 is rectangular
  • grid[i][j] is -1, 0 or 1

Expected complexity

Time
O(HW)
Space
O(HW)

Examples

gridExpected
[[1,0,0],[0,-1,0],[0,0,0]]4
[[1,-1,0],[0,-1,0]]-1
[[1,0,1],[0,0,0]]2

Hint

Hint

Run one BFS with every moldy cell in the initial queue at distance 0 (multi-source BFS); the answer is the largest distance, or -1 if a clean cell stays unvisited. Re-scanning the whole grid every minute is O(HW⋅T)O(HW \cdot T), and a winding corridor makes T≈HW/2T \approx 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 251062 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

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

No result yet. Run or submit your code.