1. Toy模板网首页
  2. > Toy博客

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

8月前 作者：闻缺陷则喜何志丹 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了【动态规划】【广度优先搜索】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]]
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数,# 算法题,数据结构与算法,动态规划,宽度优先,leetcode,二分查找,c++,算法,广度优先搜索

输出：4
解释：上图展示了到达右下角格子经过的 4 个格子。
示例 2：
输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
输出：3
解释：上图展示了到达右下角格子经过的 3 个格子。
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数,# 算法题,数据结构与算法,动态规划,宽度优先,leetcode,二分查找,c++,算法,广度优先搜索

示例 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;

};

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数,# 算法题,数据结构与算法,动态规划,宽度优先,leetcode,二分查找,c++,算法,广度优先搜索

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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 网格图中最少访问的格子数,# 算法题,数据结构与算法,动态规划,宽度优先,leetcode,二分查找,c++,算法,广度优先搜索文章来源地址https://www.toymoban.com/news/detail-760170.html

到了这里，关于【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 每天一道leetcode：1466. 重新规划路线（图论&中等&广度优先遍历）

    每天一道leetcode：1466. 重新规划路线（图论&中等&广度优先遍历）

    n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条

    2024年02月12日
    浏览(36)
  • 【BFS三维路径规划】广度优先搜索算法无人机三维路径规划【含Matlab源码 270期】

    【BFS三维路径规划】广度优先搜索算法无人机三维路径规划【含Matlab源码 270期】

    获取代码方式1： 完整代码已上传我的资源：【三维路径规划】基于matlab广度优先搜索算法无人机三维路径规划【含Matlab源码 270期】 获取代码方式2： 付费专栏Matlab路径规划（初级版） 备注： 点击上面蓝色字体付费专栏Matlab路径规划（初级版），扫描上面二维码，付费29.9元

    2024年02月02日
    浏览(40)
  • 2023-8-28 图中点的层次(树与图的广度优先遍历)

    2023-8-28 图中点的层次(树与图的广度优先遍历)

    题目链接：图中点的层次

    2024年02月11日
    浏览(33)
  • 深度优先搜索与动态规划|543, 124, 687

    深度优先搜索与动态规划|543, 124, 687

    好久没写二叉树了，主要还是看遍历的顺序是什么样的。 这个有点绕不出来。绕一遍， root -10 进去，root.left是root 9，root.right是root 20 root 9 进去得到的return是9，res更新得到9 root 20进去，root.left是root 15，root.right是root 7 root 15进去得到的return是15，res更新得到15 root 7进去得到的

    2024年02月13日
    浏览(32)
  • 【图论--搜索篇】宽度优先搜索，广度优先搜索

    【图论--搜索篇】宽度优先搜索，广度优先搜索

    今日语录： 成功是一种心态，如果你相信自己能做到，那你已经迈出成功的第一步。

    2024年01月24日
    浏览(35)
  • 快来看看萌新小白学习动态规划、深度优先搜索、贪心

    快来看看萌新小白学习动态规划、深度优先搜索、贪心

    由于比赛临近，老师给我们布置了一些LeetCode算法题目，但是我在学完Hello算法的数据结构部分之后，就跑去学习算法第四版了。被一些安全比赛耽误，算法的学习进度比较慢，通过这篇文章就可以体现出我的技术还是比较菜的，还望谅解，哈哈。 LeetCode题目#206 反转链表 这是

    2024年04月14日
    浏览(35)
  • 为什么深度优先搜索可以判定简单图中是否有环，而宽度优先搜索不行？

    为什么深度优先搜索可以判定简单图中是否有环，而宽度优先搜索不行？

    1，首先可以肯定的是，对于无向图而言，宽搜和深搜都能判断是否有环。 简要说明一下，假如一个无向图有环，那么在宽搜的过程中，能搜到已经访问过的结点。如果一个无向图没有环（参考无向树），那么它的宽度优先搜索过程中，是不会访问到已访问过的结点的。 对于

    2024年02月14日
    浏览(44)
  • 【深度优先搜索】和【广度优先搜索】的区别介绍

    【深度优先搜索】和【广度优先搜索】的区别介绍

    深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的图搜索算法。它们的主要区别在于搜索的方式和顺序不同。 从某个节点出发，沿着一条路径直到底部，然后返回到前一个节点，继续搜索下一条路径，直到搜索完整张图。DFS使用栈或者

    2024年02月06日
    浏览(30)
  • 动态规划+深度优先搜索—，java面试问的问题都答上来了

    动态规划+深度优先搜索—，java面试问的问题都答上来了

    第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。 第二行只有一个数，表示能挖到的最多地雷数。 输入输出样例 输入 1 5 10 8 4 7 6 1 1 1 0 0 0 0 1 1 1 输出 1 1 3 4 5 27 说明/提示 【题目来源】 NOIP 1996 提高组第三题 解题代码：（动态规

    2024年04月11日
    浏览(29)
  • 深度优先搜索（DFS）和广度优先搜索（BFS）

    深度优先搜索（DFS）和广度优先搜索（BFS）

    代码随想录 深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。 先给大家说一下两者大概的区别： 如果搜索是以接近起始状态的程序依次扩展状态的，叫广度优先搜索。 如果扩展是首先扩展

    2024年02月02日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包