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

相关文章

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后
阅读更多...
本地搭建DeepSeek-R1、WebUI的完整过程及访问

本地搭建DeepSeek-R1、WebUI的完整过程及访问

《本地搭建DeepSeek-R1、WebUI的完整过程及访问》：本文主要介绍本地搭建DeepSeek-R1、WebUI的完整过程及访问的相关资料,DeepSeek-R1是一个开源的人工智能平台,主... 目录背景       搭建准备基础概念搭建过程访问对话测试总结背景       最近几年，人工智能技术
阅读更多...
Ollama整合open-webui的步骤及访问

Ollama整合open-webui的步骤及访问

《Ollama整合open-webui的步骤及访问》：本文主要介绍如何通过源码方式安装OpenWebUI,并详细说明了安装步骤、环境要求以及第一次使用时的账号注册和模型选择过程,需要的朋友可以参考... 目录安装环境要求步骤访问选择PjrIUE模型开始对话总结 安装官方安装地址：https://docs.
阅读更多...
Java使用POI-TL和JFreeChart动态生成Word报告

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven
阅读更多...
Java导出Excel动态表头的示例详解

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法，代码不进
阅读更多...
vue基于ElementUI动态设置表格高度的3种方法

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div，原理是将表格的高度设置成外层div的高度，所以外层的div需要
阅读更多...
解读静态资源访问static-locations和static-path-pattern

解读静态资源访问static-locations和static-path-pattern

《解读静态资源访问static-locations和static-path-pattern》本文主要介绍了SpringBoot中静态资源的配置和访问方式,包括静态资源的默认前缀、默认地址、目录结构、访... 目录静态资源访问static-locations和static-path-pattern静态资源配置
阅读更多...
SpringBoot实现动态插拔的AOP的完整案例

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程（AOP）是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插
阅读更多...
Java访问修饰符public、private、protected及默认访问权限详解

Java访问修饰符public、private、protected及默认访问权限详解

《Java访问修饰符public、private、protected及默认访问权限详解》：本文主要介绍Java访问修饰符public、private、protected及默认访问权限的相关资料,每... 目录前言1. public 访问修饰符特点：示例：适用场景：2. private 访问修饰符特点：示例：
阅读更多...
VUE动态绑定class类的三种常用方式及适用场景详解

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式（对象添加：情景一）2.动态添加一个class样式（字符串添加：情
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2