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

本文涉及知识点

C++BFS算法

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++**实现。