【动态规划】【广度优先搜索】LeetCode: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 <= 10⁵

1 <= m * n <= 10⁵

0 <= grid[i][j] < m * n

grid[m - 1][n - 1] == 0

广度优先搜索和二分查找

时间复杂度

O(mnlogmax(m,n))。遍历每个单格时间复杂度O(nm)，处理一个单格O(n)+O(m)。暴力方法的时间复杂度O(nmk)，极端情况下超时。

变量解析


vRows	各行没有处理的单格的列号
vCols	各列没有处理的单格行号
vDis	各单格距离起点的距离
que	需要处理邻居的单格

核心代码

class Solution {
public:
int minimumVisitedCells(vector<vector>& grid) {
m_r = grid.size();
m_c = grid.front().size();
vector<set> vRows(m_r), vCols(m_c);
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (r + c == 0)
{
continue;
}
vRows[r].emplace©;
vCols[c].emplace®;
}
}
vector vDis(m_c * m_r,-1);
vDis[0] = 1;
queue<pair<int, int>> que;
que.emplace(0, 0);
auto Do = [&](int iDis,const int r, const int c)
{
vDis[m_c * r + c] = iDis + 1;
que.emplace(r, c);
};
while (que.size())
{
const auto [r, c] = que.front();
que.pop();
const int len = grid[r][c];
const int dis = vDis[m_c * r + c];
{//右跳
auto it = vRows[r].lower_bound©;
auto ij = vRows[r].upper_bound(c + len);
for (auto tmp = it; tmp != ij; ++tmp)
{
Do(dis, r, *tmp);
vCols[*tmp].erase®;
}
vRows[r].erase(it, ij);
}
{
auto it = vCols[c].lower_bound®;
auto ij = vCols[c].upper_bound(r + len);
for (auto tmp = it; tmp != ij; ++tmp)
{
Do(dis, *tmp,c);
vRows[*tmp].erase©;
}
vCols[c].erase(it, ij);
}
}
return vDis.back();
}
int m_r, m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<vector<int>> grid;
  {
    Solution slu;
    grid = { {3,4,2,1},{4,2,3,1},{2,1,0,0},{2,4,0,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(4, res);
  }
  {
    Solution slu;
    grid = { {3,4,2,1},{4,2,1,1},{2,1,1,0},{3,4,1,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(3, res);
  }
  {
    Solution slu;
    grid = { {2,1,0},{1,0,0} };
    auto res = slu.minimumVisitedCells(grid);
    Assert(-1, res);
  }
}

动态规划

广度优先搜索是基于动态规划实现的，如果不修改广度优先的实现，无需突出动态规划。经典广度优先搜索时，先处理距离起点近的，再处理距离远点的。是为了保证动态规划的无后效性。通俗的说：就是每个运算的前提条件都已经计算完毕。距离为iDis的单格显然是距离iDis-1单格的邻居，计算iDis的单格时，显然要计算完所有距离为iDis-1的单格。本题只右移和下移，先行后列，行列都是从小到大，也可以保证无后效性。优化枚举顺序后，就不再是广度优先搜索了，变成的普通的动态规划。

时间复杂度

O(mnlogmax(n,m))。

变量解析


rowMinHeap	当前行可以到达的列和总共经过的单格数-1
colMinHeaps	各列可以到达的行和总共经过的单格数-1

用小根堆记录经过的单格数和列号。由于列号是增加的，所有如果堆顶的列号小于当前列号，则对应小于后面的列号，可以永久删除。删除堆顶列号过小的元素后，堆顶元素就是最小经过的单格树。

代码

class Solution {
public:
  typedef priority_queue<pair<int,int>, vector<pair<int, int>>, greater<>> HTYPE;
  int minimumVisitedCells(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid.front().size();
    vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));    
    vector< HTYPE> colMinHeaps(m_c);
    for (int r = 0; r < m_r; r++)
    { 
      HTYPE rowMinHeap;
      auto Add = [&](const int r, const int c, int iNewDis)
      {
        vDis[r][c] = iNewDis;
        rowMinHeap.emplace(iNewDis, c + grid[r][c]);
        colMinHeaps[c].emplace(iNewDis, r + grid[r][c]);
      };
      for (int c = 0; c < m_c; c++)
      {
        if (r + c == 0)
        {
          Add(r, c, 1);
          continue;
        }
        while (rowMinHeap.size() && (rowMinHeap.top().second < c))
        {
          rowMinHeap.pop();
        }
        while (colMinHeaps[c].size() && (colMinHeaps[c].top().second < r ))
        {
          colMinHeaps[c].pop();
        }
        int iPreMin = INT_MAX;
        if (rowMinHeap.size())
        {
          iPreMin = min(iPreMin, rowMinHeap.top().first);
        }
        if (colMinHeaps[c].size())
        {
          iPreMin = min(iPreMin, colMinHeaps[c].top().first);
        }
        if (INT_MAX == iPreMin)
        {
          continue;
        }
        Add(r, c, iPreMin + 1);
      }
    }   
    return vDis.back().back();
  }
  int m_r, m_c;
};

单调向量（有序向量)

可以逆向考虑，从终点到起点。这样可以记录可以到达单元格的行（列）和经过的单格数。在保持数据的单调的情况下，行（列）递减，单格数递增。新增有利条件：行（列）插入的顺序也递减。这意味者可以用单调向量。

代码

class Solution {
public:
  int minimumVisitedCells(vector<vector<int>>& grid) {
    m_r = grid.size();
    m_c = grid.front().size();
    vector<vector<int>> vDis(m_r, vector<int>(m_c, -1));
    vector< vector<pair<int,int>>> cols(m_c);//列（行）号按降序排除，距离按升序排列
    for (int r = m_r-1; r >= 0 ; r-- )
    {
      vector<pair<int, int>> row;
      auto Add = [&](const int r, const int c, int iNewDis)
      {
        vDis[r][c] = iNewDis;
        while (row.size() && (row.back().first >= iNewDis))
        {
          row.pop_back();
        }
        row.emplace_back(iNewDis,c);
        while (cols[c].size() && (cols[c].back().first >= iNewDis))
        {
          cols[c].pop_back();
        }
        cols[c].emplace_back(iNewDis, r);
      };
      auto Cmp = [&](const pair<int, int>& pr, int rc)
      {
        return pr.second > rc;
      };
      for (int c = m_c-1 ; c >= 0 ;c--)
      {
        if (r + c + 2 == m_r+m_c )
        {
          Add(r, c, 1);
          continue;
        }       
        int iPreMin = INT_MAX;
        auto it = std::lower_bound(row.begin(), row.end(), c + grid[r][c], Cmp);
        if (row.end() != it )
        {
          iPreMin = min(iPreMin, it->first);
        }
        auto ij = std::lower_bound(cols[c].begin(), cols[c].end(), r + grid[r][c], Cmp);
        if (cols[c].end() != ij )
        {
          iPreMin = min(iPreMin, ij->first);
        }
        if (INT_MAX == iPreMin)
        {
          continue;
        }
        Add(r, c, iPreMin + 1);
      }
    }
    return vDis.front().front();
  }
  int m_r, m_c;
};

2023年8月版

typedef std::priority_queue<std::pair<int, int>,vector<std::pair<int, int>>,std::greater<std::pair<int, int>> > QUE;
class Solution {
public:
int minimumVisitedCells(vector<vector>& grid) {
m_r = grid.size();
m_c = grid[0].size();
vector<vector> vVis(m_r, vector(m_c,INT_MAX));
vVis[0][0] = 1;
vector< std::multiset> setCols(m_c);
vector< QUE> vDelCols(m_c);
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
auto& setCol = setCols[c];
auto& vDelCol = vDelCols[c];
while (vDelCol.size() && (vDelCol.top().first == r))
{
setCol.erase(setCol.find(vDelCol.top().second));
vDelCol.pop();
}
}
std::multiset setRow;
QUE vDelRow;
auto Add = [&](int r, int c, int dis, int value)
{
if (INT_MAX == dis)
{
return;
}
setRow.emplace(dis);
vDelRow.emplace(c + value + 1, dis);
setCols[c].emplace(dis);
vDelCols[c].emplace(r + value + 1, dis);
};
for (int c = 0; c < m_c; c++)
{
if (r + c == 0)
{
Add(0, 0, vVis[0][0], grid[r][c]);
continue;
}
while (vDelRow.size() && (vDelRow.top().first == c))
{
setRow.erase(setRow.find(vDelRow.top().second));
vDelRow.pop();
}
if (setRow.size())
{
vVis[r][c] = min(vVis[r][c],*setRow.begin()+1);
}
auto& setCol = setCols[c];
if (setCol.size())
{
vVis[r][c] = min(vVis[r][c], *setCol.begin() + 1);
}
if (INT_MAX == vVis[r][c])
{
continue;
}
Add(r, c, vVis[r][c], grid[r][c]);
}
}
int iRet = vVis.back().back();
return (INT_MAX == iRet) ? -1 : iRet;
}
int m_r, m_c;
};

其它方法

可以用有向图并集查找，寻找没有删除的元素。r1和r2连接，表示[r1,r2)已经全部删除，直接处理r2。

2023年9月版

class Solution {
public:
int minimumVisitedCells(vector<vector>& grid) {
m_r = grid.size(), m_c = grid[0].size();
if (m_r * m_c == 1)
{
return 1;
}
vector<vector<std::pair<int,int>>> vvRowMinDis(m_c); // 每列的单调栈
int iRet = m_iNotMay;
for (int r = m_r - 1; r >= 0; r–)
{
std::vector<std::pair<int, int>> vColMinDis;//列号越来越小，值越来越大
for (int c = m_c - 1; c >= 0; c–)
{
auto& sta = vvRowMinDis[c];
if ((m_r - 1 == r) && (m_c - 1 == c))
{
vColMinDis.emplace_back(c, 1);
sta.emplace_back(r, 1);
continue;
}
int iCurDis = m_iNotMay;
//处理右移
auto it = std::lower_bound(vColMinDis.begin(), vColMinDis.end(), c + grid[r][c], [](const std::pair<int, int>& p1, int a)
{return p1.first > a; });
if (vColMinDis.end() != it)
{
const int iDis = it->second + 1;
iCurDis = min(iCurDis, iDis);
}
//处理左移
auto ij = std::lower_bound(sta.begin(), sta.end(), r + grid[r][c], [](const std::pair<int, int>& p1, int a)
{return p1.first > a; });
if (sta.end() != ij)
{
const int iDis = ij->second + 1;
iCurDis = min(iCurDis, iDis);
}
if (m_iNotMay == iCurDis)
{
continue;
}
while (sta.size() && (sta.back().second >= iCurDis))
{
sta.pop_back();
}
sta.emplace_back(r, iCurDis);
while (vColMinDis.size() && (vColMinDis.back().second >= iCurDis))
{
vColMinDis.pop_back();
}
vColMinDis.emplace_back(c, iCurDis);
if (r + c == 0)
{
iRet = iCurDis;
}
}
}
return (iRet >= m_iNotMay ) ? -1 : iRet;
}
int m_r, m_c;
const int m_iNotMay = 1000 * 1000 * 1000;
};

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的基础知识点

题目

广度优先搜索和二分查找

时间复杂度

变量解析

核心代码

测试用例

动态规划

时间复杂度

变量解析

代码

单调向量（有序向量)

代码

2023年8月版

其它方法

2023年9月版

测试环境

热门文章

最新文章

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的基础知识点

题目

广度优先搜索和二分查找

时间复杂度

变量解析

核心代码

测试用例

动态规划

时间复杂度

变量解析

代码

单调向量（有序向量)

代码

2023年8月版

其它方法

2023年9月版

测试环境

热门文章

最新文章

相关电子书

相关实验场景