当前位置：网站首页>[leetcode周赛]第300场——6110. 网格图中递增路径的数目-较难

[leetcode周赛]第300场——6110. 网格图中递增路径的数目-较难

2022-07-03 18:35:00 【51CTO】

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

难度困难6收藏分享切换为英文接收动态反馈

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

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

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

示例 1：

[leetcode周赛]第300场——6110. 网格图中递增路径的数目-较难_leetcode周赛

      
      
       
       输入：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 。
      
      
      
      
       
       1.
       
       2.
       
       3.
       
       4.
       
       5.
       
       6.
       
       7.

示例 2：

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

提示：

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

题解

方法一：暴力递归解法

思路：

很简单，就是暴力递归遍历，可惜只过来34/36个测试用例，第35个超时了。很蛋疼，第一次参加周赛，第四题因为超时没过，有点不开心~~

第一次参加周赛，显示排名1325~~，截图记录一下

[leetcode周赛]第300场——6110. 网格图中递增路径的数目-较难_网图_02

[leetcode周赛]第300场——6110. 网格图中递增路径的数目-较难_记忆化_03

       
       class 
       
       Solution {
       
       public:
       
       int 
       
       mod 
       
       = 
       
       1e9 
       
       + 
       
       7;
       
       void 
       
       path(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       grid, 
       
       int 
       
       x, 
       
       int 
       
       y, 
       
       int 
       
       &
       
       res, 
       
       int 
       
       pre)
       
{
       
       if (
       
       y 
       
       >= 
       
       grid.
       
       size() 
       
       || 
       
       x 
       
       >= 
       
       grid[
       
       0].
       
       size() 
       
       || 
       
       x 
       
       < 
       
       0 
       
       || 
       
       y 
       
       < 
       
       0)
       
  {
       
       return;
       
  }
       
       if (
       
       grid[
       
       y][
       
       x] 
       
       <= 
       
       pre)
       
  {
       
       return;
       
  }
       
       res 
       
       = (
       
       res 
       
       + 
       
       1) 
       
       % 
       
       mod;
       
       int 
       
       cur 
       
       = 
       
       grid[
       
       y][
       
       x];
       
       path(
       
       grid, 
       
       x 
       
       - 
       
       1, 
       
       y, 
       
       res, 
       
       cur);
       
       path(
       
       grid, 
       
       x 
       
       + 
       
       1, 
       
       y, 
       
       res, 
       
       cur);
       
       path(
       
       grid, 
       
       x, 
       
       y 
       
       - 
       
       1, 
       
       res, 
       
       cur);
       
       path(
       
       grid, 
       
       x, 
       
       y 
       
       + 
       
       1, 
       
       res, 
       
       cur);
       
}
       
       int 
       
       countPaths(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       grid)
       
{
       
       if (
       
       grid.
       
       size() 
       
       == 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       if (
       
       grid[
       
       0].
       
       size() 
       
       == 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       int 
       
       res 
       
       = 
       
       0;
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       v(
       
       grid.
       
       size(), 
       
       std::vector
       
       <
       
       int
       
       >(
       
       grid[
       
       0].
       
       size(), 
       
       0));
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       grid.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       for (
       
       int 
       
       k 
       
       = 
       
       0; 
       
       k 
       
       < 
       
       grid[
       
       0].
       
       size(); 
       
       ++
       
       k)
       
    {
       
       path(
       
       grid, 
       
       k, 
       
       i, 
       
       res, 
       
       INT_MIN);
       
    }
       
  }
       
       // return (res + grid.size() * grid[0].size()) % mod;
       
       return 
       
       res;
       
}
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.

方法二：记忆化解法

后来想了下，用一个数组记录一下每个路径的值即可，当已经访问过后直接返回就可以了。我们使用dp[y][x]表示坐标x、y为七点的坐标所有的搜索路径。说实话，这个题目是真的不难~~~

代码如下：

       
       int 
       
       path(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       grid, 
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       v, 
       
       int 
       
       x, 
       
       int 
       
       y)
       
{
       
       if (
       
       y 
       
       >= 
       
       grid.
       
       size() 
       
       || 
       
       x 
       
       >= 
       
       grid[
       
       0].
       
       size() 
       
       || 
       
       x 
       
       < 
       
       0 
       
       || 
       
       y 
       
       < 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       // 如果已经计算过，则直接返回
       
       if (
       
       v[
       
       y][
       
       x] 
       
       != 
       
       0)
       
  {
       
       return 
       
       v[
       
       y][
       
       x];
       
  }
       
       int 
       
       direct[
       
       4][
       
       2] 
       
       = {
       
       0, 
       
       1, 
       
       0, 
       
       -
       
       1, 
       
       1, 
       
       0, 
       
       -
       
       1, 
       
       0};
       
       // 四个搜索方向
       
       v[
       
       y][
       
       x] 
       
       = 
       
       1;
       
       // <--- 假设四周的元素都不大于它，则只有1个路径
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       4; 
       
       ++
       
       i)
       
  {
       
       int 
       
       next_x 
       
       = 
       
       direct[
       
       i][
       
       0] 
       
       + 
       
       x;
       
       int 
       
       next_y 
       
       = 
       
       direct[
       
       i][
       
       1] 
       
       + 
       
       y;
       
       // 边界条件检查
       
       if (
       
       next_y 
       
       >= 
       
       grid.
       
       size() 
       
       || 
       
       next_x 
       
       >= 
       
       grid[
       
       0].
       
       size() 
       
       || 
       
       next_x 
       
       < 
       
       0 
       
       || 
       
       next_y 
       
       < 
       
       0)
       
    {
       
       continue;
       
    }
       
       // 只有递增的才需要计算
       
       if (
       
       grid[
       
       next_y][
       
       next_x] 
       
       <= 
       
       grid[
       
       y][
       
       x])
       
    {
       
       continue;
       
    }
       
       v[
       
       y][
       
       x] 
       
       = (
       
       v[
       
       y][
       
       x] 
       
       + 
       
       path(
       
       grid, 
       
       v, 
       
       next_x, 
       
       next_y)) 
       
       % 
       
       mod;
       
       // 累加四个方向的相邻长度
       
  }
       
       return 
       
       v[
       
       y][
       
       x];
       
}
       
       int 
       
       countPaths(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       grid)
       
{
       
       int 
       
       res 
       
       = 
       
       0;
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       v(
       
       grid.
       
       size(), 
       
       std::vector
       
       <
       
       int
       
       >(
       
       grid[
       
       0].
       
       size(), 
       
       0));
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       grid.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       for (
       
       int 
       
       k 
       
       = 
       
       0; 
       
       k 
       
       < 
       
       grid[
       
       0].
       
       size(); 
       
       ++
       
       k)
       
    {
       
       res 
       
       = (
       
       res 
       
       + 
       
       path(
       
       grid, 
       
       v, 
       
       k, 
       
       i)) 
       
       % 
       
       mod;
       
    }
       
  }
       
       return 
       
       res;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.