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

2023-12-15 07:44
文章标签 leetcode 动态 规划 访问 搜索 最少 优先 广度 网格 格子 图中 2617

本文主要是介绍【动态规划】【广度优先搜索】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++**实现。

这篇关于【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/495672。

相关文章

HTML5 搜索框Search Box详解

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具，能够有效提升用户体验,通过结合自动补全功能和适当的样式，可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框（Search Box）详解搜索框是一个用于输入查询内容的控件，通常用于网站或应用程
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...
如何搭建并配置HTTPD文件服务及访问权限控制

如何搭建并配置HTTPD文件服务及访问权限控制

《如何搭建并配置HTTPD文件服务及访问权限控制》：本文主要介绍如何搭建并配置HTTPD文件服务及访问权限控制的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、安装HTTPD服务二、HTTPD服务目录结构三、配置修改四、服务启动五、基于用户访问权限控制六、
阅读更多...
MyBatis编写嵌套子查询的动态SQL实践详解

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可
阅读更多...
Mybatis嵌套子查询动态SQL编写实践

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》：本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL
阅读更多...
SpringBoot实现Kafka动态反序列化的完整代码

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题（Topic）的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht
阅读更多...
golang实现动态路由的项目实践

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体（数据库的定义）2.预加载preload3.添加关联的方法一、动态路由1
阅读更多...
NGINX 配置内网访问的实现步骤

NGINX 配置内网访问的实现步骤

《NGINX配置内网访问的实现步骤》本文主要介绍了NGINX配置内网访问的实现步骤,Nginx的geo模块限制域名访问权限,仅允许内网/办公室IP访问,具有一定的参考价值,感兴趣的可以了解一下... 目录需求1. geo 模块配置2. 访问控制判断3. 错误页面配置4. 一个完整的配置参考文档需求我们有一
阅读更多...
C#实现访问远程硬盘的图文教程

C#实现访问远程硬盘的图文教程

《C#实现访问远程硬盘的图文教程》在现实场景中,我们经常用到远程桌面功能,而在某些场景下,我们需要使用类似的远程硬盘功能,这样能非常方便地操作对方电脑磁盘的目录、以及传送文件,这次我们将给出一个完整的... 目录引言一. 远程硬盘功能展示二. 远程硬盘代码实现1. 底层业务通信实现2. UI 实现三. De
阅读更多...
python通过curl实现访问deepseek的API

python通过curl实现访问deepseek的API

《python通过curl实现访问deepseek的API》这篇文章主要为大家详细介绍了python如何通过curl实现访问deepseek的API,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编... API申请和充值下面是deepeek的API网站https://platform.deepsee
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2