编程语言|【C++BFS 离散化】1036. 逃离大迷宫|2164

本文涉及知识点

LeetCode1036. 逃离大迷宫

在一个 106 x 106 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
示例 1：
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。
示例 2：
输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。
提示：
0 <= blocked.length <= 200
blocked[i].length == 2
0 <= xi, yi < 10⁶
source.length == target.length == 2
0 <= sx, sy, tx, ty < 10⁶
source != target
题目数据保证 source 和 target 不在封锁列表内

BFS+离散化

如果有两个或更多的空行挨在一起，只保留一行，其它空行删除。空列也是如此，对结果无影响。
对行列号进行离散化。xs记录左右边界，封锁格的列，起点列，终点列。排序去重。xs[0]编码为0，
如果 xs[i] == xs[i-1]+1,xs[i]编码=xs[i-1]的编码+1;否则xs[i]编码=xs[i-1]的编码+2;
然后BFS。
n = blocked.size 故单格数量：2n $\times$ 2n。
BFS的时间复杂度：O(nn)

代码

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;
	}
	vector<vector<int>> Dis( 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(m_r, vector<int>(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 >= m_r) || (c1 < 0) || (c1 >= 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;
	}
	 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 CMyDiscretize //离散化
		{
		public:
			CMyDiscretize(vector<int> nums)
			{
				sort(nums.begin(), nums.end());
				nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
				m_nums = nums;
				m_mValueToIndex[nums[0]] = 0;
				int iEmpty = 0;
				for (int i = 1; i < nums.size(); i++)
				{
					if (nums[i] - nums[i - 1] > 1) { iEmpty++; }
					m_mValueToIndex[nums[i]] = i+iEmpty;
				}
			}
			int operator[](const int value)const
			{
				auto it = m_mValueToIndex.find(value);
				if (m_mValueToIndex.end() == it)
				{
					return -1;
				}
				return it->second;
			}
			int size()const
			{
				return m_mValueToIndex.size();
			}
			vector<int> m_nums;
		protected:
			unordered_map<int, int> m_mValueToIndex;
		};
		class Solution {
		public:
			bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
				vector<int > xs = { source[0],target[0],0,99999 }, ys = { source[1],target[1], 0,99999 };
				for (const auto& v : blocked) {
					xs.emplace_back(v[0]);
					ys.emplace_back(v[1]);
				}
				CMyDiscretize d1(xs), d2(ys);
				const int R = d1[d1.m_nums.back()]+1;
				const int C = d2[d2.m_nums.back()]+1;
				vector<vector<int>> grid(R, vector<int>(C));
				for (const auto& v : blocked) {
					int i1 = d1[v[0]];
					int i2 = d2[v[1]];
					grid[i1][i2] = 1;
				}
				CGrid eg(R, C);
				auto Vilid = [&](int r, int c) {return 0 == grid[r][c]; };
				const auto start = make_pair(d1[source[0]], d2[source[1]]);
				const int x1 = d1[target[0]];
				const int y1 = d2[target[1]];
				auto res = eg.Dis({ start	}, Vilid, Vilid);
				return -1 != res[x1][y1] ;
			}
		};

单元测试

vector<vector<int>> blocked;
		vector<int> source,  target;
		TEST_METHOD(TestMethod1)
		{
			blocked = { {0,1},{1,0} }, source = { 0,0 }, target = { 0,2 };
			auto res = Solution().isEscapePossible(blocked, source, target);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod2)
		{
			blocked = {}, source = { 0,0 }, target = { 999999,999999 };
			auto res = Solution().isEscapePossible(blocked, source, target);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod3)
		{
			blocked = { {100005,100073},{100006,100074},{100007,100075},{100008,100076},{100009,100077},{100010,100078},{100011,100079},{100012,100080},{100013,100081},{100014,100082},{100015,100083},{100016,100084},{100017,100085},{100018,100086},{100019,100087},{100020,100088},{100021,100089},{100022,100090},{100023,100091},{100024,100092},{100025,100091},{100026,100090},{100027,100089},{100028,100088},{100029,100087},{100030,100086},{100031,100085},{100032,100084},{100033,100083},{100034,100082},{100035,100081},{100036,100080},{100037,100079},{100038,100078},{100039,100077},{100040,100076},{100041,100075},{100042,100074},{100043,100073},{100044,100072},{100043,100071},{100042,100070},{100041,100069},{100040,100068},{100039,100067},{100038,100066},{100037,100065},{100036,100064},{100035,100063},{100034,100062},{100033,100061},{100032,100060},{100031,100059},{100030,100058},{100029,100057},{100028,100056},{100027,100055},{100026,100054},{100025,100053},{100024,100052},{100023,100053},{100022,100054},{100021,100055},{100020,100056},{100019,100057},{100018,100058},{100017,100059},{100016,100060},{100015,100061},{100014,100062},{100013,100063},{100012,100064},{100011,100065},{100010,100066},{100009,100067},{100008,100068},{100007,100069},{100006,100070},{100005,100071} };
			source = {100024,100072}, target = { 999994,999990 };
			auto res = Solution().isEscapePossible(blocked, source, target);
			AssertEx(true, 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++**实现。

算法及C++答疑请加群

QQ群名片