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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/246209.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

双向无线功率传输系统MATLAB仿真

双向无线功率传输系统MATLAB仿真

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介&#xff1a; 初级侧转换器通过双向 AC/DC 转换器从电网获取电力&#xff0c;并由直流线电压 Vin 供电&#xff0c;而拾波侧被视为连接到 EV&#xff0c;并由连接到任一存储的单独直流源 Vout 表示或…
阅读更多...
ES日志分析在Win系统上的安装和使用

ES日志分析在Win系统上的安装和使用

Es日志分析三件套ElasticSearch、Kibana、logstash。 ElasticSearch 下载 官方下载地址 选择自己想要的版本下载即可。这个地方有可能下载会比较慢。可以结合迅雷做下载。 分词器下载 官方分词器下载 如果GIthub加载不出来。可以看看我的这个文章GitHub上不去怎么办&…
阅读更多...
[渗透测试学习] Sau - HackTheBox

[渗透测试学习] Sau - HackTheBox

首先是信息搜集&#xff0c;nmap扫一下 nmap -sV -sC -p- -v 10.10.11.224 发现存在两个端口&#xff0c;55555端口有http服务&#xff0c;访问一下 获得线索request-baskets版本为1.2.1&#xff0c;搜索发现存在漏洞 那么我们试试构造ssrf&#xff0c;create的时候bp抓包 构…
阅读更多...
4.11 构建onnx结构模型-Clip

4.11 构建onnx结构模型-Clip

前言 构建onnx方式通常有两种&#xff1a; 1、通过代码转换成onnx结构&#xff0c;比如pytorch —> onnx 2、通过onnx 自定义结点&#xff0c;图&#xff0c;生成onnx结构 本文主要是简单学习和使用两种不同onnx结构&#xff0c; 下面以 Clip 结点进行分析 方式 方法一…
阅读更多...
HarmonyOS(ArkTS)基础组件参数 媒体类型讲解

HarmonyOS(ArkTS)基础组件参数 媒体类型讲解

我们这里做了一个空的容器 然后 我们可以这样写 Entry Component struct Index {build() {Row() {Column() {Text("你好")Divider()Button("点击")}.width(100%)}.height(100%)} }这里 我们分别使用了三个组件 Text文本组件 Divider分割线组件 Button按钮…
阅读更多...
简说vue-router原理

简说vue-router原理

vue-router原理 hash模式 实现原理 改变描点监听描点变化 history模式 实现原理 改变url监听url变化 abstracthash 和 history 模式有什么区别&#xff1f; url 不一样原理不同 其他总结扩展 history 出现404错误 vue-router原理 vue-router是vue项目的重要组成部分&#x…
阅读更多...
STM32的基本定时器注意点

STM32的基本定时器注意点

本文介绍了STM32基本定时器3个重要的寄存器PSC、ARR、CNT&#xff0c;以及缓冲机制和计数细节。 基本定时器的框图 预分频器寄存器(TIMx_PSC)可以在运行过程中修改它的数值&#xff0c;新的预分频数值将在下一个更新事件时起作用。因为更新事件发生时&#xff0c;会把 TIMx_PS…
阅读更多...
Flink 流处理流程 API详解

Flink 流处理流程 API详解

流处理API的衍变 Storm&#xff1a;TopologyBuilder构建图的工具&#xff0c;然后往图中添加节点&#xff0c;指定节点与节点之间的有向边是什么。构建完成后就可以将这个图提交到远程的集群或者本地的集群运行。 Flink&#xff1a;不同之处是面向数据本身的&#xff0c;会把D…
阅读更多...
java实现冒泡排序及其动图演示

java实现冒泡排序及其动图演示

冒泡排序是一种简单的排序算法&#xff0c;它重复地遍历要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果它们的顺序错误就把它们交换过来。重复这个过程直到整个数列都是按照从小到大的顺序排列。 具体步骤如下&#xff1a; 比较相邻的两个元素&#xff0c;如果前…
阅读更多...
三层交换的原理

三层交换的原理

一.三层交换技术 1.什么是三层交换机 要实现vlan间通信&#xff0c;就需要路由&#xff0c;解决办法要么是二层交换机加路由器形成单臂路由&#xff0c;要么就是直接使用三层交换机。 ①什么是单臂路由&#xff1a; ②单臂路由实现不同vlan间通信的原理&#xff1a; 路由器…
阅读更多...
【C语言程序设计】函数程序设计

【C语言程序设计】函数程序设计

目录 前言 一、程序阅读 二、程序设计 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#…
阅读更多...
亚信科技AntDB数据库——深入了解AntDB-M元数据锁的实现（二）

亚信科技AntDB数据库——深入了解AntDB-M元数据锁的实现（二）

5.5 防止低优先级锁饥饿 AntDB-M按照优先级将锁又分了两类&#xff0c;用于解决低优先级锁饥饿问题。 ●独占型(hog): X, SNRW, SNW; 具有较强的不兼容性&#xff0c;优先级高&#xff0c;容易霸占锁&#xff0c;造成其他低优先级锁一直处于等待状态。 ●暗弱型(piglet): SW; …
阅读更多...
springboot获取配置文件属性值

springboot获取配置文件属性值

Value&#xff1a; 作用&#xff1a;属性注入&#xff0c;需要每个值上进行书写变量名 ConfigurationProperties 指定外部属性文件。在类上添加&#xff0c;常与ConfigurationProperties 配合使用
阅读更多...
系统登页面——大屏系统深蓝色主题

系统登页面——大屏系统深蓝色主题

加了线上验证码校验还有密码账号校验。其他的资料都放在文章末尾了。 <template xmlns"http://www.w3.org/1999/html"><div class"login"><img :src"imgBg" class"login_bg" width"100%" height"100%&q…
阅读更多...
持续集成交付CICD：CentOS 7 安装SaltStack

持续集成交付CICD：CentOS 7 安装SaltStack

目录 一、理论 1.SaltStack 二、实验 1.主机一安装master 2.主机二安装第一台minion 3.主机三安装第二台minion 4.测试SaltStack 三、问题 1.CentOS 8 如何安装SaltStack 一、理论 1.SaltStack &#xff08;1&#xff09;概念 SaltStack是基于python开发的一套C/S自…
阅读更多...
消息队列(MQ)

消息队列(MQ)

对于 MQ 来说&#xff0c;不管是 RocketMQ、Kafka 还是其他消息队列&#xff0c;它们的本质都是&#xff1a;一发一存一消费。下面我们以这个本质作为根&#xff0c;一起由浅入深地聊聊 MQ。 01 从 MQ 的本质说起 将 MQ 掰开了揉碎了来看&#xff0c;都是「一发一存一消费」&…
阅读更多...
排序算法(二)-冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序

排序算法(二)-冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序

排序算法(二) 前面介绍了排序算法的时间复杂度和空间复杂数据结构与算法—排序算法&#xff08;一&#xff09;时间复杂度和空间复杂度介绍-CSDN博客&#xff0c;这次介绍各种排序算法——冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序。 文章目录 排…
阅读更多...
【linux】SSH终端Putty配置：上传/下载、显示中文字体、自动登录

【linux】SSH终端Putty配置：上传/下载、显示中文字体、自动登录

文章目录 写在前面putty上传/下载1. 下载2. 解压和配置3. 使用sz/rz3.1 下载文件:sz3.2 上传文件:rz 显示中文字体1. 下载合适的字体2. 解压和安装3. putty配置 putty自动登录1. putty配置2. putty快捷方式配置3. 使用putty 写在后面 写在前面 一篇博客介绍了12种SSH终端工具的…
阅读更多...
【超图】SuperMap iClient3D for WebGL/WebGPU —— 单体gltf模型与Blender中的方向对应关系

【超图】SuperMap iClient3D for WebGL/WebGPU —— 单体gltf模型与Blender中的方向对应关系

作者&#xff1a;taco 在很多包含动画的场景中&#xff0c;像模拟小人的行走、模拟火车的轨迹运行&#xff0c;又或者是模拟风力发电等等等。我们通常会加一些动画模型到里面。而有的时候可能会出现&#xff0c;这火车怎么倒着走啊&#xff01;这人怎么头朝下啊。这种方向的问题…
阅读更多...
AIGC - 环境搭建

AIGC - 环境搭建

一. 硬件环境 1. 超微7048主板&#xff0c;最多可搭载4块GPU 2. 2个Intel的 Xen至强 14核 CPU 3. 目前安装了一块Nvidia 的P40 GPU&#xff0c;后续根据需要还最多可以扩展3块GPU 4. 4T机械 2T Nvme固态&#xff0c; 5. 4条64G DDR4内存条&#xff0c;共 196G内存…
阅读更多...
最新文章

Copyright @ 2022~2023