Funcia
Lv.2dpgrid

Grid Paths Around Puddles

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

Each cell of grid is 0 (free) or 1 (puddle). Moving only right or down from (0, 0) to the bottom-right cell without stepping on puddles, return the number of paths modulo 1,000,000,0071{,}000{,}000{,}007 (0 if the start or end is a puddle).

Examples

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

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≤1,0001 \le H, W \le 1{,}000; grid[i][j] is 0 or 1

Expected complexity

Time
O(HW)
Space
O(W)

Examples

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

Hint

Hint

paths[i][j] = paths[i-1][j] + paths[i][j-1] (0 on puddles), filled row by row; one row of storage is enough. Enumerating paths recursively takes as long as the number of paths.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251248 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.