您现在的位置是：首页 >其他 >【力扣周赛】第340场周赛网站首页其他

2617：网格图中最少访问的格子数

题目描述

描述：给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。
请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

示例 1：

输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
输出：4
解释：上图展示了到达右下角格子经过的 4 个格子。

示例 2：

输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
输出：3
解释：上图展示了到达右下角格子经过的 3 个格子。

示例 3：

输入：grid = [[2,1,0],[1,0,0]]
输出：-1
解释：无法到达右下角格子。

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0

解题思路

网格图中最少访问的格子数：最直观的想法是，使用dp[i][j]表示矩阵第i行第j列格子到达右下角格子所需要的最少步数，其中m表示矩阵行数，n表示矩阵列数，dp[m-1][n-1]初始化为0，grid[i][j]=0且i!=m-1且j!=n-1对应的dp[i][j]初始化为无穷大，即表示无法到达，其他元素初始化为-1。设计traverse(i,j,grid,dp,m,n)函数表示第i行第j列格子到达右下角格子所需的最少步数，该函数采用记忆化搜索方法。如果dp[i][j]不等于-1，则表示其已经被初始化过，故直接返回dp[i][j]；反之分别遍历从第i行向下移动1到grid[i][j]格其到达右下角的最少步数和从第j列向右移动1到grid[i][j]格其到达右下角的最少步数，其中当前第i行第j列到达右下角的最少步数等于上述中的最少步数加一，然后存储dp[i][j]并返回。最后根据返回值是INT_MAX还是非INT_MAX来决定返回-1还是res+1。(超时)

// 求grid[i][j]到目标节点的最少步数
int traverse(int i,int j,vector<vector<int>> &grid,vector<vector<int>> &dp,int m,int n)
{
   if(dp[i][j]!=-1) //已经被赋值
      return dp[i][j];
   long minx=INT_MAX;
   // 遍历当前行i以及其下边对应grid[i][j]
   for(int k=1;k<=grid[i][j]&&i+k<m;k++)
   {
      minx=min((long)traverse(i+k,j,grid,dp,m,n)+1,minx);
   }
   // 遍历当前列j以及其右边对应grid[i][j]
   for(int k=1;k<=grid[i][j]&&j+k<n;k++)
   {
      minx=min((long)traverse(i,j+k,grid,dp,m,n)+1,minx);
   }
   dp[i][j]=(int)minx;
   return dp[i][j];
}
int minimumVisitedCells(vector<vector<int>>& grid) 
{
   int m=grid.size();
   int n=grid[0].size();
   vector<vector<int>> dp(m,vector<int>(n,-1));
   // 初始化非目标0
   for(int i=0;i<m;i++)
   {
      for(int j=0;j<n;j++)
      {
         if(grid[i][j]==0)
           dp[i][j]=INT_MAX;
      }
   }
   // 初始化目标0
   dp[m-1][n-1]=0;
   int res=traverse(0,0,grid,dp,m,n);
   return res==INT_MAX?-1:res+1;
}

优化：上述方法中存在的一个问题是太多重复遍历，假设第一个元素为3，则既要向右3个也要向下3个，其在向右和向下的过程中，又需要递归的向右和向下，则会出现很多重叠。基于以上分析，就需要在原本的BFS广度优先搜索的基础上，再使用row记录当前行还尚未遍历的最小列，并使用col记录当前列还尚未遍历的最小行。(有几个测试用例解答错误)

class Solution {
public:
    int minimumVisitedCells(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        // row表示当前行尚未遍历的最小列
        vector<int> row(m,0);
        // col表示当前列尚未遍历的最小行
        vector<int> col(n,0);
        // dp[i][j]表示从(0,0)到当前格子的步数
        vector<vector<int>> dp(m,vector<int>(n,-1));
        dp[0][0]=0;
        queue<pair<int,int>> que;
        // 压入第一个元素
        que.push({0,0});
        // 当队列不为空 层序遍历
        while(!que.empty())
        {
            // 取出坐标
            auto [x,y]=que.front();
            que.pop();
            // 取出元素
            int val=grid[x][y];
            //遍历行 避免重复 不能越界
            for(int xx=max(x+1,col[y]);xx<=min(x+val,m-1);xx++)
            {
                //尚未遍历
                if(dp[xx][y]==-1)
                {
                    dp[xx][y]=dp[x][y]+1;
                    que.push({xx,y});
                }
            }
            //更新当前列尚未遍历的最小行
            col[y]=min(x+val+1,m-1);
            //遍历列
            for(int yy=max(y+1,row[x]);yy<=min(y+val,n-1);yy++)
            {
                //尚未遍历
                if(dp[x][yy]==-1)
                {
                    dp[x][yy]=dp[x][y]+1;
                    que.push({x,yy});
                }
            }
            //更新当前行尚未遍历的最小列
            row[x]=min(y+val+1,n-1);
        }
        //加上最开始的格子
        return dp[m-1][n-1]==-1?-1:dp[m-1][n-1]+1;
    }
};