网格图中递增路径的数目

2328. 网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从任意格子出发，达到任意格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 10⁹ + 7 取余后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

示例 1：

输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。

示例 2：

输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countPaths(vector<vector<int>>& grid) { } };

golang 解法, 执行用时: 148 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-27 22:22:17

var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func countPaths(grid [][]int) (ans int) {
	const mod int = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if f[i][j] != -1 {
			return f[i][j]
		}
		res := 1
		for _, d := range dirs {
			if x, y := i+d.x, j+d.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j] {
				res = (res + dfs(x, y)) % mod
			}
		}
		f[i][j] = res
		return res
	}
	for i, row := range grid {
		for j := range row {
			ans = (ans + dfs(i, j)) % mod
		}
	}
	return
}

java 解法, 执行用时: 33 ms, 内存消耗: 54.6 MB, 提交时间: 2023-10-27 22:22:05

class Solution {
    static final int MOD = (int) 1e9 + 7;
    static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    int[][] grid, f;

    public int countPaths(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        f = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(f[i], -1);
        var ans = 0;
        for (var i = 0; i < m; ++i)
            for (var j = 0; j < n; ++j)
                ans = (ans + dfs(i, j)) % MOD;
        return ans;
    }

    int dfs(int i, int j) {
        if (f[i][j] != -1) return f[i][j];
        var res = 1;
        for (var d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j])
                res = (res + (dfs(x, y))) % MOD;
        }
        return f[i][j] = res;
    }
}

cpp 解法, 执行用时: 252 ms, 内存消耗: 38.9 MB, 提交时间: 2023-10-27 22:21:55

class Solution {
    const int MOD = 1e9 + 7;
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int countPaths(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int f[m][n]; memset(f, -1, sizeof(f));
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (f[i][j] != -1) return f[i][j];
            int res = 1;
            for (auto &d : dirs) {
                int x = i + d[0], y = j + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j])
                    res = (res + (dfs(x, y))) % MOD;
            }
            return f[i][j] = res;
        };
        int ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                ans = (ans + dfs(i, j)) % MOD;
        return ans;
    }
};

python3 解法, 执行用时: 1128 ms, 内存消耗: 109.4 MB, 提交时间: 2023-10-27 22:21:43

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i: int, j: int) -> int:
            res = 1
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:
                    res += dfs(x, y)
            return res % MOD
        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD

上一题

下一题

详情