【动态规划】【广度优先】LeetCode2258:逃离火灾_网站优化分享

您的位置：上海毫米网络优化公司 > 网站优化分享 >

作者推荐

视频算法专题

本文涉及的基础知识点

二分查找算法合集

动态规划汇总

二分查找

题目

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

0 表示草地。

1 表示着火的格子。

2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到相邻的草地格子。每次你移动之后，着火的格子会扩散到所有不是墙的相邻格子。

请你返回你在初始位置可以停留的最多分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你总是能到达安全屋，请你返回 10⁹。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为相邻格子。

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

解释：上图展示了初始网格图。

注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。

所以返回 10⁹。

提示：

m == grid.length

n == grid[i].length

2 <= m, n <= 300

4 <= m * n <= 2 * 10⁴

grid[i][j] 是 0 ，1 或者 2 。

grid[0][0] == grid[m - 1][n - 1] == 0

分析

动态规划

时间复杂度: O(n)。BFS时间复杂度O(n)，计算最晚时间O(1)。

我么把每个单格看成一个图论的一个节点，那么二维动态规划就变成了一维动态规划。我们通过广度优先可以计算出人和火到达各点时间，如果无法到达，记做10⁹的时间达到，单格数不超过10⁴，所以不可能这么晚到达的。

原理


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

令安全屋上面或左面的格子为终点。能从通过某个终点到达安全屋的充分必要条件是：

一，比火早到终点。

二，人到达终点时，火没到安全屋。

只需要考虑终点格子，不需要考虑中间格子。如果中间某个格子火追上人，则终点格子火一定能追上人。火跟着人走。

大致模块和步骤

一，封装单源BFS和多源BFS。

二，初始邻接表和初始着火点。

三，计算人和火到达各点时间。

四，计算最晚出发时间。

特殊情况分析


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

代码

核心代码

class Solution {
public:
	int maximumMinutes(vector>& grid) {
		m_r = grid.size();
		m_c = grid.front().size();
		vector> vNeiB(m_r*m_c);
		auto Add =[&](const auto & n1, const auto & n2)
		{
			vNeiB[n1].emplace_back(n2);
			vNeiB[n2].emplace_back(n1);
		};
		vector 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{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
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}
template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}
int main()
{
	vector> 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

class Solution {

public:

int maximumMinutes(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& grid)

{

m_vNotCanVisit.assign(m_r, vector(m_c, m_iNotMay));

std::queue> 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> 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>& curFire, int r, int c, const 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& grid)

{

std::queue> prePeo;

vector vHasDo(m_r, vector(m_c));

prePeo.emplace(0, 0);

for (; prePeo.size(); iStep++)

{

std::queue> 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& vHasDo,std::queue>& curPeo, int r, int c, const 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 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> m_que;

public:

vector m_bCanVisit;

vector m_vDis;

const int m_r, m_c;

};

class Solution {

public:

int maximumMinutes(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:逃离火灾,第1张

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境：

VS2022 C++17

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

晋中新闻网官网黑龙江建设信息网泉州网站建设系统武汉网站制作哪家好学做网站太原网站建设方案开发

上一篇：二叉树详解(深度优先遍历、前序，中序，后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

下一篇：初级数据结构（五）——树和二叉树的概念

作者推荐

本文涉及的基础知识点

题目

分析

动态规划

原理

大致模块和步骤

特殊情况分析

代码

核心代码

测试用例

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

2023年9月旧代码

扩展阅读

视频课程

相关下载

测试环境