【动态规划】【广度优先搜索】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。

相关文章

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
C#如何动态创建Label,及动态label事件

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》：本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点：switch中的生成我们的label事件接着，
阅读更多...
SpringCloud动态配置注解@RefreshScope与@Component的深度解析

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.
阅读更多...
MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL？1.2 动态SQL的优点1.3 动态S
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
使用Dify访问mysql数据库详细代码示例

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》：本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务，并使用ngrok暴露到公网。#sql_tools.pyfrom
阅读更多...
Javascript访问Promise对象返回值的操作方法

Javascript访问Promise对象返回值的操作方法

《Javascript访问Promise对象返回值的操作方法》这篇文章介绍了如何在JavaScript中使用Promise对象来处理异步操作,通过使用fetch()方法和Promise对象,我们可以从... 目录在Javascript中，什么是Promise1- then() 链式操作2- 在之后的代码中使
阅读更多...
基于Canvas的Html5多时区动态时钟实战代码

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》：本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示，通过Canvas的API，可以绘制出6个不同城市的时钟，并且这些时钟可以动态转动，每个时钟上都会标注出对应的24小时制时间，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
Python使用DeepSeek进行联网搜索功能详解

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例：图像分类1.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2