#2328

Number of Increasing Paths in a Grid

expert · 1235 · lc hard +32 · verified · 57.4% accepted · 2,108 likes · top 53%

Description

You are given an m x n integer matrix grid. From any cell you may move to any of its 4 adjacent neighbors.

Return the number of strictly increasing paths in the grid, where any cell can be the start or end. Paths are different if they differ in at least one visited cell. Return the count modulo 10⁹ + 7.

Example 1:

Input: grid = [[1,1],[3,4]]

Output: 8

Explanation: The strictly increasing paths are:

- Paths with length 1: [1], [1], [3], [4].

- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].

- Paths with length 3: [1 -> 3 -> 4].

The total number of paths is 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[1],[2]]

Output: 3

Explanation: The strictly increasing paths are:

- Paths with length 1: [1], [2].

- Paths with length 2: [1 -> 2].

The total number of paths is 2 + 1 = 3.

Code

1

2

3

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int: