Uphill-Only Walks

Hard

You are given a height map as a rectangular matrix heights. In one step you may move to the cell directly above, below, left or right, but only if it is **strictly higher** than the current one. A walk may start at any cell and end at any cell; a walk of a single cell counts too. Two walks are different if their sequences of visited cells differ. Return the number of distinct walks modulo 10⁹ + 7.

Example 1

heights=[[1, 2], [2, 3]] → 10

Four single-cell walks, four two-cell walks (from 1 to either 2, and from either 2 to 3) and two three-cell walks: 1 → 2 → 3 through either 2. That is 10.

Example 2

heights=[[5, 5, 5]] → 3

Neighbouring cells are equal, so no strictly rising step exists; only the three single-cell walks remain.

Example 3

heights=[[3, 2, 1]] → 6

Constraints

1 ≤ len(heights), len(heights[0]) ≤ 1000
len(heights) · len(heights[0]) ≤ 10⁵
1 ≤ heights[i][j] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort Memoization Array Dynamic Programming Matrix

Similar problems

Longest Uphill Walk Hard Mouse, Cat and Cheese Hard Letter Order From a Dictionary Hard Ball Into the Hole Hard Six-Cell Tile Slider Hard

Input

heights=[[1, 2], [2, 3]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.