【动态规划】【广度优先】LeetCode2258:逃离火灾

这篇具有很好参考价值的文章主要介绍了【动态规划】【广度优先】LeetCode2258:逃离火灾。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

本文涉及的基础知识点

二分查找算法合集
动态规划汇总
二分查找

题目

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ,它表示一个网格图。每个格子为下面 3 个值之一:
0 表示草地。
1 表示着火的格子。
2 表示一座墙,你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ,你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟,你可以移动到 相邻 的草地格子。每次你移动 之后 ,着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数,且停留完这段时间后你还能安全到达安全屋。如果无法实现,请你返回 -1 。如果不管你在初始位置停留多久,你 总是 能到达安全屋,请你返回 109
注意,如果你到达安全屋后,火马上到了安全屋,这视为你能够安全到达安全屋。
如果两个格子有共同边,那么它们为 相邻 格子。
示例 1:
输入:grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出:3
解释:上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。
示例 2:
输入:grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出:-1
解释:上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子,所以无法安全到达安全屋。
所以返回 -1 。
示例 3:
输入:grid = [[0,0,0],[2,2,0],[1,2,0]]
输出:1000000000
解释:上图展示了初始网格图。
注意,由于火被墙围了起来,所以无论如何你都能安全到达安全屋。
所以返回 109
提示:
m == grid.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 104
grid[i][j] 是 0 ,1 或者 2 。
grid[0][0] == grid[m - 1][n - 1] == 0

分析

动态规划

时间复杂度: O(n)。BFS时间复杂度O(n),计算最晚时间O(1)。
我么把每个单格看成一个图论的一个节点,那么二维动态规划就变成了一维动态规划。我们通过广度优先可以计算出人和火到达各点时间,如果无法到达,记做109的时间达到,单格数不超过104,所以不可能这么晚到达的。

原理

安全屋 人必须比火早到或同时到达
非安全屋 人必须比火早到

令安全屋上面或左面的格子为终点。能从通过某个终点到达安全屋的充分必要条件是:
一,比火早到终点。
二,人到达终点时,火没到安全屋。
只需要考虑终点格子,不需要考虑中间格子。如果中间某个格子火追上人,则终点格子火一定能追上人。火跟着人走。

大致模块和步骤

一,封装单源BFS和多源BFS。
二,初始邻接表和初始着火点。
三,计算人和火到达各点时间。
四,计算最晚出发时间。

特殊情况分析

人无法到达终点 fireEnd<=peoEnd,过 fireEnd-peoEnd-1 为负数 peoStart为负数
人能到达终点 火无法到达终点、完全屋 fireEnd为10^9 peoEnd小于mn 故 fireEnd-peoEnd-1 远大于mn
人能到达终点 火无法到达终点、能到完全屋 结果正确 计算的结果是:比火到安全屋提前一天到终点,实际结果也是。

代码

核心代码

class Solution {
public:
	int maximumMinutes(vector<vector<int>>& grid) {
		m_r = grid.size();
		m_c = grid.front().size();
		vector<vector<int>> vNeiB(m_r*m_c);
		auto Add =[&](const auto & n1, const auto & n2)
		{
			vNeiB[n1].emplace_back(n2);
			vNeiB[n2].emplace_back(n1);
		};
		vector<int> vFire;
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				if (2 == grid[r][c])
				{
					continue;
				}
				const int mask = m_c * r + c;
				if (1 == grid[r][c])
				{
					vFire.emplace_back(mask);
				}				
				if (r && (2 != grid[r-1][c]))
				{
					Add(mask, mask - m_c);
				}
				if( c && ( 2 != grid[r][c-1]))
				{
					Add(mask, mask - 1);
				}
			}
		}
		CBFSDis disPeo(vNeiB, vector<int>{0});
		CBFSDis disFire(vNeiB, vFire);
		const int fireEnd1 = min(disFire.m_vDis[m_r * m_c - 1 - m_c], disFire.m_vDis.back());
		const int fireEnd2 = min(disFire.m_vDis[m_r * m_c - 1 - 1], disFire.m_vDis.back());
		const int peoStart1 = fireEnd1 - disPeo.m_vDis[m_r * m_c - 1 - m_c] - 1;
		const int peoStart2 = fireEnd2 - disPeo.m_vDis[m_r * m_c - 1 - 1] - 1;
		const int iRet = max(peoStart1, peoStart2);
		if (iRet < 0)
		{
			return -1;
		}
		if (iRet > m_r * m_c)
		{
			return 1e9;
		}
		return iRet;
	}
	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;
	long long budget;
	{
		Solution slu;	
		grid = { {0,2,0,0,0,0,0},{0,0,0,2,2,1,0},{0,2,0,0,1,2,0},{0,0,2,2,2,0,2},{0,0,0,0,0,0,0} };
		auto res = slu.maximumMinutes(grid);
		Assert(3, res);
	}
	{
		Solution slu;
		grid = { {0,0,0,0},{0,1,2,0},{0,2,0,0} };
		auto res = slu.maximumMinutes(grid);
		Assert(-1, res);
	}
	{
		Solution slu;
		grid = { {0,0,0},{2,2,0},{1,2,0} };
		auto res = slu.maximumMinutes(grid);
		Assert(1000000000, res);
	}
	{
		Solution slu;
		grid = { {0,2,0,0,1},{0,2,0,2,2},{0,2,0,0,0},{0,0,2,2,0},{0,0,0,0,0} };
		auto res = slu.maximumMinutes(grid);
		Assert(0, res);
	}
	{
		Solution slu;
		grid = { {0,0,0,0,0,0},{0,2,2,2,2,0},{0,0,0,1,2,0},{0,2,2,2,2,0},{0,0,0,0,0,0} };
		auto res = slu.maximumMinutes(grid);
		Assert(1, res);
	}
	//CConsole::Out(res);
}

2023年3月旧代码:二分查找实现

如果t1 <t2,t2能到达安全屋,则t1一定可能。我们寻找能达到的最大t,左闭右开空间。

class Solution {
public:
int maximumMinutes(vector<vector>& grid) {
m_r = grid.size();
m_c = grid[0].size();
InitNotCanVisit(grid);
if (!bfs(0, grid))
{
return -1;
}
if (bfs(30*1000, grid))
{
return 1000 * 1000 * 1000;
}
int left = 0, right = 30 * 1000;
while (right > left + 1)
{
const int iMid = left + (right - left) / 2;
if (bfs(iMid, grid))
{
left = iMid;
}
else
{
right = iMid;
}
}
return left;
}
void InitNotCanVisit(const vector<vector>& grid)
{
m_vNotCanVisit.assign(m_r, vector(m_c, m_iNotMay));
std::queue<std::pair<int, int>> preFire;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (0 != grid[r][c])
{
m_vNotCanVisit[r][c] = 0;
}
if (1 == grid[r][c])
{
preFire.emplace(r, c);
}
}
}
for (int iStep = 0; preFire.size(); iStep++)
{
std::queue<std::pair<int, int>> curFire;
while (preFire.size())
{
const int r = preFire.front().first;
const int c = preFire.front().second;
preFire.pop();
Fire(curFire, r + 1, c, grid,iStep);
Fire(curFire, r - 1, c, grid, iStep);
Fire(curFire, r, c + 1, grid, iStep);
Fire(curFire, r, c - 1, grid, iStep);
}
preFire.swap(curFire);
}
m_vNotCanVisit.back().back()++;
}
void Fire(std::queue<std::pair<int, int>>& curFire, int r, int c, const vector<vector>& grid,const int iStep)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (m_iNotMay != m_vNotCanVisit[r][c])
{
return;
}
m_vNotCanVisit[r][c] = iStep;
curFire.emplace(r, c);
}
bool bfs(int iStep, const vector<vector>& grid)
{
std::queue<std::pair<int, int>> prePeo;
vector<vector> vHasDo(m_r, vector(m_c));
prePeo.emplace(0, 0);
for (; prePeo.size(); iStep++)
{
std::queue<std::pair<int, int>> curPeo;
while (prePeo.size())
{
const int r = prePeo.front().first;
const int c = prePeo.front().second;
if ((m_r - 1 == r) && (m_c - 1 == c))
{
return true;
}
prePeo.pop();
MovePeo(vHasDo, curPeo, r+1, c, grid, iStep);
MovePeo(vHasDo, curPeo, r - 1, c, grid, iStep);
MovePeo(vHasDo, curPeo, r, c + 1, grid, iStep);
MovePeo(vHasDo, curPeo, r, c - 1, grid, iStep);
}
prePeo.swap(curPeo);
}
return false;
}
void MovePeo(vector<vector>& vHasDo,std::queue<std::pair<int, int>>& curPeo, int r, int c, const vector<vector>& grid, const int iStep)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (iStep >= m_vNotCanVisit[r][c])
{
return;
}
if (vHasDo[r][c])
{
return;
}
vHasDo[r][c] = true;
curPeo.emplace(r, c);
}
int m_r;
int m_c;
const int m_iNotMay = 1000 * 100;
vector<vector> m_vNotCanVisit;
};

2023年9月旧代码

class CBFSGridDist
{
public:
CBFSGridDist(int r, int c) :m_r®, m_c©,m_vDis(r, vector(c, -1)), m_bCanVisit(r,vector(c,true))
{
}
void BFS()
{
while (m_que.size())
{
const auto [r, c] = m_que.front();
m_que.pop();
const int iDis = m_vDis[r][c] + 1;
Move(r,c,r + 1, c, iDis);
Move(r, c, r - 1, c, iDis);
Move(r, c, r, c + 1, iDis);
Move(r, c, r, c - 1, iDis);
};
}
void AddDist(int r, int c, int iDis)
{
m_vDis[r][c] = iDis;
m_que.emplace(r, c);
}
protected:
void Move (int preR, int preC, int r, int c, int iDis)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (-1 != m_vDis[r][c]) {
return;
}
if (!m_bCanVisit[r][c])
{
return;
}
AddDist(r, c, iDis);
};
queue<pair<int, int>> m_que;
public:
vector<vector> m_bCanVisit;
vector<vector> m_vDis;
const int m_r, m_c;
};

class Solution {
public:
int maximumMinutes(vector<vector>& grid) {
m_r = grid.size();
m_c = grid.front().size();
CBFSGridDist bfsPeo(m_r, m_c), bfsFire(m_r, m_c);
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (2 == grid[r][c])
{
bfsFire.m_bCanVisit[r][c] = false;
bfsPeo.m_bCanVisit[r][c] = false;
}
if (1 == grid[r][c])
{
bfsFire.AddDist(r, c, 0);
}
}
}
bfsPeo.AddDist(0, 0, 0);
bfsFire.BFS();
bfsPeo.BFS();
const int iPeo = bfsPeo.m_vDis.back().back();
if (-1 == iPeo)
{//人无法到达
return -1;
}
const int iFire = bfsFire.m_vDis.back().back();
if (-1 == iFire)
{//火无法到达
return 1000 * 1000 * 1000;
}
if (iPeo > iFire)
{//火比人先到
return -1;
}
const int p1 = bfsPeo.m_vDis[m_r - 2].back();
const int p2 = bfsPeo.m_vDis.back()[m_c - 2];
const int f1 = bfsFire.m_vDis[m_r - 2].back();
const int f2 = bfsFire.m_vDis.back()[m_c - 2];
int iRet = -1;
if ( p1 > 0)
{//人通过上面进入完全屋
const int cur = min(f1<0?1e9:f1, (f2<0?1e9:f2) + 1) - (p1 + 1);
iRet = max(iRet, cur);
}
if (p2 > 0)
{//人通过左边进入安全屋
const int cur = min((f1 < 0 ? 1e9 : f1) +1, (f2 < 0 ? 1e9 : f2)) - (p2+1);
iRet = max(iRet, cur);
}
return iRet;
}
int m_r, m_c;
};

【动态规划】【广度优先】LeetCode2258:逃离火灾,数据结构与算法,# 算法题,动态规划,宽度优先,算法,c++,二分查找,LeetCode,火灾

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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

【动态规划】【广度优先】LeetCode2258:逃离火灾,数据结构与算法,# 算法题,动态规划,宽度优先,算法,c++,二分查找,LeetCode,火灾文章来源地址https://www.toymoban.com/news/detail-751436.html

到了这里,关于【动态规划】【广度优先】LeetCode2258:逃离火灾的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 大话数据结构-图的深度优先遍历和广度优先遍历

      图的遍历分为深度优先遍历和广度优先遍历两种。   深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS,深度优先遍历,是指从某一个顶点开始,按照一定的规则,访问并记录下一个未访问顶点。对于非连通图,则是按连通分量,采用同一规则进行深度优

    2024年02月04日
    浏览(58)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(57)
  • 【数据结构】图的广度优先遍历

    广度优先遍历,类似于树的层次遍历,又是熟悉的队列实现。首先将第一个顶点添加到队列中,然后讲该顶点的所有邻接顶点都加入队列中,再将该顶点输出。如此重复直到遍历完整个图。 Q:队列,用于存放顶点。 front,rear:队头和队尾指针,用于入队和出队。 p:工作指针,用

    2024年02月05日
    浏览(48)
  • 数据结构——图篇(邻接矩阵、邻接表、深度优先搜索、广度优先搜索)

    描述 图比树更为复杂,展现的是一种多对多的关系,图的结构是任意两个数据对象之间都可能存在某种特定的关系的数据结构 概念 顶点 : 基本介绍 顶点集合表示为V集合,要求图中顶点至少要有一个,即V集合不能为空集。通常使用|V|来表示顶点的个数,通常使用E(V)来表示

    2024年02月04日
    浏览(40)
  • 【数据结构】图的遍历:广度优先(BFS),深度优先(DFS)

    目录 1、广度优先(BFS) 算法思想  广度优先生成树  知识树  代码实现  2、深度优先(DFS) 算法思想  深度优先生成树 知识树  代码实现           图的广度优先遍历(BFS)是一种遍历图的算法,其思想是从起始顶点开始遍历图,先访问起始顶点的所有直接邻居,然

    2024年02月04日
    浏览(63)
  • (超详细)C++图的深度优先遍历、广度优先遍历(数据结构)

            根据下图,编写代码实现图的深度优先遍历和广度优先遍历。          按照英文字母顺序,以邻接表为存储结构,实现图的深度优先和广度优先遍历。遍历的顺序从顶点a开始。 以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。   (1)从顶点a,

    2024年02月08日
    浏览(59)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(50)
  • LeetCode-200. 岛屿数量【深度优先搜索 广度优先搜索 并查集 数组 矩阵】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月14日
    浏览(38)
  • 【数据结构】广度优先遍历(BFS)模板及其讲解

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录   🎁定义 🎁遍历方法  🎁根据题目来理解BFS 🏳️‍🌈走迷宫 🏳️‍🌈思路 🏳️‍🌈代码(BFS模板) 🏳️‍🌈分

    2024年02月06日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包