首页 > 编程语言 >【C++BFS算法 二分查找】2812. 找出最安全路径

【C++BFS算法 二分查找】2812. 找出最安全路径

时间：2024-07-31 17:28:51浏览次数：10  
标签：return 2812 int auto C++ BFS start vector grid

本文涉及知识点

C++BFS算法
C++二分查找

LeetCode2812. 找出最安全路径

给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid ，其中 (r, c) 表示：
如果 grid[r][c] = 1 ，则表示一个存在小偷的单元格
如果 grid[r][c] = 0 ，则表示一个空单元格
你最开始位于单元格 (0, 0) 。在一步移动中，你可以移动到矩阵中的任一相邻单元格，包括存在小偷的单元格。
矩阵中路径的 安全系数 定义为：从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。
返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。
单元格 (r, c) 的某个 相邻 单元格，是指在矩阵中存在的 (r, c + 1)、(r, c - 1)、(r + 1, c) 和 (r - 1, c) 之一。
两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | + | b - y | ，其中 |val| 表示 val 的绝对值。
示例 1：
在这里插入图片描述

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：0
解释：从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。
示例 2：
在这里插入图片描述

输入：grid = [[0,0,1],[0,0,0],[0,0,0]]
输出：2
解释：
上图所示路径的安全系数为 2：

  • 该路径上距离小偷所在单元格（0，2）最近的单元格是（0，0）。它们之间的曼哈顿距离为 | 0 - 0 | + | 0 - 2 | = 2 。
    可以证明，不存在安全系数更高的其他路径。
    示例 3：
    在这里插入图片描述

输入：grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
输出：2
解释：
上图所示路径的安全系数为 2：

  • 该路径上距离小偷所在单元格（0，3）最近的单元格是（1，2）。它们之间的曼哈顿距离为 | 0 - 1 | + | 3 - 2 | = 2 。
  • 该路径上距离小偷所在单元格（3，0）最近的单元格是（3，2）。它们之间的曼哈顿距离为 | 3 - 3 | + | 0 - 2 | = 2 。
    可以证明，不存在安全系数更高的其他路径。

提示：
1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] 为 0 或 1
grid 至少存在一个小偷

二分查找

一，BFS出各单格距离小偷的位置（层次）leve。
二，二分查找。Check(mid) 是否存在安全系数为mid或更大的路径。随着mid从0到leve[0][0]，Check的返回值逐步由true，变成false。我们寻找最后一个true。Check函数的大致步骤：
a,连通距离小偷大于等与mid的单格。
b，看右下角的层次是否大于等于0。

代码

第一版（超时）

class CGrid {
public:
	CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}
	vector<vector<pair<int, int>>> NeiBo(std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4)
	{
		vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= m_r))
			{
				return;
			}
			if ((c < 0) || (c >= m_c))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[Mask(preR, preC)].emplace_back(r, c);
			}
		};

		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				for (int k = 0; k < iConnect; k++)
				{
					Move(r, c, r + s_Moves[k][0], c + s_Moves[k][1]);
				}
			}
		}
		return vNeiBo;
	}
	 void EnumGrid(std::function<void(int, int)> call)
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				call(r, c);
			}
		}
	}	
	 vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {
		 vector<pair<int, int>> ret;
		 for (int r = 0; r < m_r; r++)
		 {
			 for (int c = 0; c < m_c; c++)
			 {
				 if (fun(r, c)) {
					 ret.emplace_back(r, c);
				 }
			 }
		 }
		 return ret;
	 }
	inline int Mask(int r, int c) { return  m_c * r + c; }
	const int m_r, m_c;
	const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};

class CBFSLeve {
public :
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]]+1;
				start.emplace_back(next);
			}
		}
		return leves;
	}
	static vector<vector<int>> Leve(CGrid& grid, vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4 ) {
		auto neiBo = grid.NeiBo(funVilidCur, funVilidCur, iConnect);
		vector<vector<int>> leves(grid.m_r, vector<int>(grid.m_c, -1));
		for (const auto& [r,c] : start) {
			leves[r][c] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			const int iMask = grid.Mask(start[i].first, start[i].second);
			for (const auto& [r1,c1] : neiBo[iMask]) {
				if (-1 != leves[r1][c1]) { continue; }
				leves[r1][c1] = leves[start[i].first][start[i].second] + 1;
				start.emplace_back(r1,c1);
			}
		}
		return leves;
	}
};

template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist( _Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd( _Pr pr)
	{
		int leftInclude = m_iMin;
		int right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};


class Solution {
		public:
			int maximumSafenessFactor(vector<vector<int>>& grid) {
				CGrid ng(grid.size(),grid[0].size());
				auto start = ng.GetPos([&](int r, int c) {return grid[r][c] == 1; });
				auto vilid = [&](int r, int c) {return true; };
				auto leve = CBFSLeve::Leve(ng, start,vilid, vilid);
				auto Check = [&](int mid) {
					auto vilid1 = [&](int r, int c) {return leve[r][c] >= mid; };
					auto leve1 = CBFSLeve::Leve(ng, { {0,0 } }, vilid1, vilid1);
					return leve1.back().back() >= 0;
				};
				CBinarySearch<int> bs(0, leve[0][0]);
				return bs.FindEnd(Check);
			}
		};

第二版

中间过程，求临接表浪费很多时间，省略后，速度提高几倍。就可以过了。许多单格和起点不连通，无需计算。

class CGrid {
public:
	CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}
	template<class Fun1,class Fun2>
	vector<vector<pair<int, int>>> NeiBo(Fun1 funVilidCur, Fun2 funVilidNext, int iConnect = 4)
	{
		vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				if (!funVilidCur(r, c))continue;
				auto& v = vNeiBo[Mask(r, c)];
				if ((r > 0)&& funVilidNext(r-1, c)) {
					v.emplace_back(r-1, c);
				}
				if ((c > 0) && funVilidNext(r , c - 1)) {
					v.emplace_back(r, c - 1);
				}
				if ((r+1 < m_r ) && funVilidNext(r + 1, c)) {
					v.emplace_back(r + 1, c);
				}
				if ((c+1 <m_c ) && funVilidNext(r, c + 1)) {
					v.emplace_back(r, c + 1);
				}
			}
		}
		return vNeiBo;
	}
	 void EnumGrid(std::function<void(int, int)> call)
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				call(r, c);
			}
		}
	}	
	 vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {
		 vector<pair<int, int>> ret;
		 for (int r = 0; r < m_r; r++)
		 {
			 for (int c = 0; c < m_c; c++)
			 {
				 if (fun(r, c)) {
					 ret.emplace_back(r, c);
				 }
			 }
		 }
		 return ret;
	 }
	inline int Mask(int r, int c) { return  m_c * r + c; }
	const int m_r, m_c;
	const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};

class CBFSLeve {
public :
	static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {
		vector<int> leves(neiBo.size(), -1);
		for (const auto& s : start) {
			leves[s] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			for (const auto& next : neiBo[start[i]]) {
				if (-1 != leves[next]) { continue; }
				leves[next] = leves[start[i]]+1;
				start.emplace_back(next);
			}
		}
		return leves;
	}

	static vector<vector<int>> Dis(CGrid& grid, vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, const int& iConnect = 4 ) {
		static short dir[8][2] = { {0, 1}, {1, 0}, {-1, 0},{ 0, -1},{1,1},{1,-1},{-1,1},{-1,-1} };
		vector<vector<int>> vDis(grid.m_r, vector<int>(grid.m_c, -1));
		for (const auto& [r,c] : start) {
			vDis[r][c] = 0;
		}
		for (int i = 0; i < start.size(); i++) {
			const auto [r,c] = start[i];
			if (!funVilidCur(r, c)) { continue; }
			for (int k = 0; k < iConnect; k++) {
				const int r1 = r + dir[k][0];
				const int c1 = c + dir[k][1];
				if ((r1 < 0) || (r1 >= grid.m_r) || (c1 < 0) || (c1 >= grid.m_c)) { continue; }
				if (funVilidNext(r1, c1)&&(-1 == vDis[r1][c1])) {
					start.emplace_back(r1, c1);
					vDis[r1][c1]= vDis[r][c] + 1;
				}
			}
		}
		return vDis;
	}
};


template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist( _Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd( _Pr pr)
	{
		int leftInclude = m_iMin;
		int right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};


		class Solution {
		public:
			int maximumSafenessFactor(vector<vector<int>>& grid) {
				CGrid ng(grid.size(),grid[0].size());		
				auto start = ng.GetPos([&](int r, int c) {return grid[r][c] == 1; });
				auto vilid = [&](int r, int c) {return true; };
				auto dis = CBFSLeve::Dis(ng, start,vilid, vilid);
				auto Check = [&](int mid) {
					auto vilid1 = [&](int r, int c) {return dis[r][c] >= mid; };
					auto dis2 = CBFSLeve::Dis(ng, { {0,0} }, vilid1, vilid1);
					return dis2.back().back() >= 0;
				};
				CBinarySearch<int> bs(0, min(dis[0][0],dis.back().back()));
				return bs.FindEnd(Check);
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod1)
		{
			grid = { {1} };
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod15)
		{
			grid = { {1,0,0},{0,0,0},{0,0,1} };
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod16)
		{
			grid = { {0,0,1},{0,0,0},{0,0,0} };
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod17)
		{
			grid = { {0,0,0,1},{0,0,0,0},{0,0,0,0},{1,0,0,0} };
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod18)
		{
			grid.assign(400, vector<int>(400));
			grid[0][0] = 1;
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod19)
		{
			grid.assign(400, vector<int>(400));
			grid.back().back() = 1;
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod20)
		{
			grid.assign(400, vector<int>(400));
			grid[0].back() = 1;
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(399, res);
		}
		TEST_METHOD(TestMethod21)
		{
			grid.assign(400, vector<int>(400));
			grid.back()[0] = 1;
			auto res = Solution().maximumSafenessFactor(grid);
			AssertEx(399, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

标签：return,2812,int,auto,C++,BFS,start,vector,grid
From： https://blog.csdn.net/he_zhidan/article/details/140659862

相关文章

  • 【C++】构造函数的深入学习
    一、初始化列表C++提供初始化列表语法用来初始化属性语法：构造函数（）：属性1（值1），属性2（值2）...{}classPeople{public://传统初始化操作Person(inta,intb,intc){A=a;B=b;C=c;}//初始化列表初始化属性Pers......
  • 【C++】对象模型和this指针
    一、成员变量和成员函数分开存储只有非静态成员变量才属于类的对象上①C++编译器会给每一个空对象分配一个字节的空间，为了区分空对象占内存的位置classPerson{}voidtest(){PersonP;//空类（类中什么也没有）中的空对象所占内存空间为1cout<<sizeof(P......
  • C++面向对象编程解析
    文章目录1.概述2.作用解析3.概念解析1.类和对象2.封装（Encapsulation）3.继承（Inheritance）4.多态（Polymorphism）1.概述C++是在C语言的基础上增加了面向对象编程（OOP）特性的编程语言。面向对象编程是一种编程范式，通过将程序组织成对象的集合，这些对象包含数据和行......
  • 关于使用C#注入C++的封装DLL后打印内容乱码
    最近因需要，用C++写了个钩子的DLL，一切工作测试通过后，放到C#里使用P/Invoke调用，发现部分乱码，最后反复测试，才发现一个问题，原来SetWindowsHookEx这个函数，也是分A版和W版，最后换了就正常了，附上对比。。乱码[DllImport("user32.dll",SetLastError=true]publicstaticex......
  • 搭建 STM32 网关服务器的全流程：集成嵌入式 C++、TCP/IP 通信、Flash 存储及 JWT 认证（
    引言随着物联网（IoT）技术的快速发展，基于STM32的服务器（类似网关）在数据采集、设备控制等方面的应用越来越广泛。本文将介绍搭建一个基于STM32的服务器所需的技术栈，以及详细的搭建步骤和代码示例。技术栈介绍在搭建基于STM32的服务器时，我们需要用到以下技术栈和组件：1.硬......
  • 【C++】auto
    1、概念auto不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。注意：使用auto变量时必须对其进行初始化，在编译阶段编译器需要根据初始化表达式来推导auto的实际类型。因此，auto并非是一种“类型”的声明，而是一个类型......
  • 三种语言实现二维差分（C++/Python/Java)
    题目输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1,y1,x2,y2,c其中(x1,y1)和(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。请你将进行完所有操作后的矩阵输出。输入格式第一行包含整数n,......
  • 碰撞检测 | 矩形增量膨胀安全走廊模型(附C++/Python仿真)
    目录0专栏介绍1安全走廊建模的动机2矩形增量膨胀算法3算法仿真3.1C++实现3.2Python实现0专栏介绍......
  • C++学习04day--引用
    案例代码：会发现最后程序执行完，打印X，最后还是100C++与C语言类似，C++中函数的参数是形式参数，即是实参的拷贝，所以修改的不是实参，所以X不改变，因此我们引入引用引用：即为某个已存在的变量名，引用变量与被引用变量公用一块内存空间，比如土豆和马铃薯都是同一种东西的不同命名。通过在......
  • 三种语言实现差分（C++/Python/Java)
    题目输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l,r,c表示将序列中[l,r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数n和m。第二行包含n个整数，表示整数序列。接下来m行，每行包含三个整数l，r，c，表......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99