【动态规划】【广度优先搜索】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 <= 105
1 <= m * n <= 105
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;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！