【动态规划】【广度优先】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;
};

扩展阅读

视频课程

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

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

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

相关文章

极智一周 | AI 算力国产化、通义开源、Gemini、鸿蒙、蔚来 And so on

极智一周 | AI 算力国产化、通义开源、Gemini、鸿蒙、蔚来 And so on

欢迎关注我的公众号 [极智视界]&#xff0c;获取我的更多技术分享 大家好&#xff0c;我是极智视界&#xff0c;带来本周的 [极智一周]&#xff0c;关键词&#xff1a;AI 算力国产化、通义开源、Gemini、鸿蒙、蔚来 And so on。 邀您加入我的知识星球「极智视界」&#xff0c;…
阅读更多...
【Linux】make/Makefile --- 自动化构建项目的工具

【Linux】make/Makefile --- 自动化构建项目的工具

目录 一、make/Makefile的简单使用 二、Makefile 的语法规则 三、实现的原理 3.1 make/Makefile识别文件新旧 3.2 .PHONY修饰的伪目标总是被执行 3.3 make/Makefile是具有依赖性的推导能力的 四、语法技巧 五、注意事项 Linux中自动化构建项目最简单的方式&#xff1a;…
阅读更多...
Linux系统---简易伙伴系统

Linux系统---简易伙伴系统

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、题目要求 1.采用C语言实现 2.伙伴系统采用free_area[11]数组来组织。要求伙伴内存最小为一个页面&#xff0c;页面大小为4KB…
阅读更多...
C语言习题

C语言习题

写一个函数&#xff0c;输入一个四位数字&#xff0c;要求输出这四个数字字符&#xff0c;但每两个数字间空一个空格。如输入1990&#xff0c;输出1 9 9 0 如下&#xff1a; #include<stdio.h> void Print(int n) { if(n>9) { Print(n/10); } printf("%d "…
阅读更多...
ssm的健身房预约系统（有报告）。Javaee项目。ssm项目。

ssm的健身房预约系统（有报告）。Javaee项目。ssm项目。

演示视频&#xff1a; ssm的健身房预约系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Spring…
阅读更多...
【trino权威指南】使用trino详解：trino client安装、查询sql、DBeaver连接trino、java通过JDBC连接trino

【trino权威指南】使用trino详解：trino client安装、查询sql、DBeaver连接trino、java通过JDBC连接trino

文章目录 一. Trino CLI1. 安装client2. 使用client执行sql 二. JDBC driver 连接Trino1. 通过DBeaver用户界面连接2. JDBC Driver in java2.1. 环境配置2.2. 注册和配置driver2.3. 连接参数2.4. 查询例子 一. Trino CLI 1. 安装client Trino CLI提供了一个基于终端的交互式s…
阅读更多...
H264之NALU结构详解

H264之NALU结构详解

摘要&#xff1a;本文详细描述了AVC的NALU的码流结构&#xff0c;以及各个层面上NALU详细的构成。   关键字&#xff1a;AVC&#xff0c;NALU 1 NALU简介 NAL层即网络抽象层&#xff08;Network Abstraction Layer&#xff09;&#xff0c;是为了方便在网络上传输的一种抽象…
阅读更多...
tomcat篇---第四篇

tomcat篇---第四篇

系列文章目录 文章目录 系列文章目录前言一、为什么我们将tomcat称为Web容器或者Servlet容器 ？二、tomcat是如何处理Http请求流程的？三、tomcat结构目录有哪些?前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这…
阅读更多...
Mysql索引一篇就够了

Mysql索引一篇就够了

索引 定义 索引是对数据库表中一列或者多列的值进行排序的结构。 目的 数据库索引好比一本书的目录&#xff0c;提高查询效率。但是为表设置索引要付出相应的代价&#xff1a; 增加了数据库的存储空间 在插入和修改时需花费更多的时间&#xff08;因为索引也要随之变动&#…
阅读更多...
带有 RaspiCam 的 Raspberry Pi 监控和延时摄影摄像机

带有 RaspiCam 的 Raspberry Pi 监控和延时摄影摄像机

一、说明 一段时间以来&#xff0c;我一直想构建一个运动激活且具有延时功能的树莓派相机&#xff0c;但从未真正找到我喜欢的案例。我在thingiverse上找到了这个适合树莓派和相机的好案例。它是为特定的鱼眼相机设计的&#xff0c;但从模型来看&#xff0c;我拥有的廉价中国鱼…
阅读更多...
【基于Python的二手车数据可视化平台的设计与实现】

【基于Python的二手车数据可视化平台的设计与实现】

基于Python的二手车数据可视化平台的设计与实现 前言数据获取与处理网络爬虫数据存储 可视化平台的设计与实现Flask框架数据可视化 创新点结语 前言 随着社会的不断发展&#xff0c;二手车市场也逐渐成为一个备受关注的领域。为了更好地为二手车的买家和卖家提供信息&#xff…
阅读更多...
Pycharm设置为中文版

Pycharm设置为中文版

文章目录 关注公众号&#xff1a;『AI学习星球』 算法学习、4对1辅导、论文辅导或核心期刊可以通过公众号或CSDN滴滴我 在使用Pycharm的时候&#xff0c;会发现里面的菜单栏以及内容都是英文为主。 英文版的优点是&#xff1a;比较稳定&#xff0c;其次大家都在用英文版&…
阅读更多...
MobaXterm成功连接到开发环境后，过一段时间会自动断开。

MobaXterm成功连接到开发环境后，过一段时间会自动断开。

问题现象 MobaXterm成功连接到开发环境后&#xff0c;过一段时间会自动断开。 原因 配置MobaXterm工具时&#xff0c;没有勾选“SSH keepalive”或专业版MobaXterm工具的“Stop server after”时间设置太短。
阅读更多...
Android 样式小结

Android 样式小结

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览三、使用3.1 创建并应用样式3.2 创建并…
阅读更多...
zabbix 通过 odbc 监控 mssql

zabbix 通过 odbc 监控 mssql

1、环境 操作系统&#xff1a;龙蜥os 8.0 zabbix&#xff1a;6.0 mssql&#xff1a;2012 2、安装odbc 注意&#xff1a;需要在zabbix server 或者 zabbix proxy 安装 odbc驱动程序 dnf -y install unixODBC unixODBC-devel3、安装mssql驱动程序 注意&#xff1a;我最开始尝试…
阅读更多...
【Unity】Addressable包资源加载失败：CRC Mismatch.

【Unity】Addressable包资源加载失败：CRC Mismatch.

Error while downloading Asset Bundle: CRC Mismatch. 是资源下载校验失败&#xff0c;但是资源和上次打包的资源是一样的。没有排查到原因&#xff0c;在谷歌搜索后看到 大概就是指Unity版本修改后打包&#xff0c;会破坏原来的CRC信息&#xff0c;导致导报出来的资源无法通…
阅读更多...
一篇文章带你了解并使用mybatis框架

一篇文章带你了解并使用mybatis框架

mybatis简介&#xff1a; MyBatis 是一款优秀的持久层框架&#xff0c;它支持自定义 SQL、存储过程以及高级映射。MyBatis 免除了几乎所有的 JDBC 代码以及设置参数和获取结果集的工作。MyBatis 可以通过简单的 XML 或注解来配置和映射原始类型、接口和 Java POJO&#xff08;P…
阅读更多...
python彩色螺旋四边形 青少年电子学会等级考试 中小学生python编程等级考试二级真题答案解析2022年6月

python彩色螺旋四边形 青少年电子学会等级考试 中小学生python编程等级考试二级真题答案解析2022年6月

目录 python彩色螺旋四边形 一、题目要求 二、算法分析 三、程序代码
阅读更多...
深度学习之全面了解预训练模型

深度学习之全面了解预训练模型

在本专栏中&#xff0c;我们将讨论预训练模型。有很多模型可供选择&#xff0c;因此也有很多考虑事项。 这次的专栏与以往稍有不同。我要回答的问题全部源于 MathWorks 社区论坛&#xff08;ww2.mathworks.cn/matlabcentral/&#xff09;的问题。我会首先总结 MATLAB Answers …
阅读更多...
Python time模块详解

Python time模块详解

time 模块主要包含各种提供日期、时间功能的类和函数。该模块既提供了把日期、时间格式化为字符串的功能&#xff0c;也提供了从字符串恢复日期、时间的功能。 在 Python 的交互式解释器中先导入 time 模块&#xff0c;然后输入 [e for e in dir(time) if not e.startswith(_)…
阅读更多...
最新文章

Copyright @ 2022~2023