1036. 逃离大迷宫 - 力扣（LeetCode） (leetcode-cn.com)
题目
在一个 1e6 x 1e6 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，但不能走禁止通行的方格。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
数据范围
-
0 <= blocked.length <= 200
-
blocked[i].length == 2
-
0 <= xi, yi < 106
-
source.length == target.length == 2
-
0 <= sx, sy, tx, ty < 106
-
source != target
-
题目数据保证 source 和 target 不在封锁列表内
题意
判断在一个二维表格中，是否可以从起始地点走到目标地点，不能经过被封锁的格子
思路
二维矩阵寻路问题，一般来说都是搜索
在不考虑题目数据范围的情况下，肯定是直接BFS从起始地址开始搜索，但是此题数据范围太大，如果直接搜索最坏的时间复杂度为1e12，肯定会超时。
因此想办法优化，可以发现二维矩阵非常大，但是禁止通行的点比较少，最多只有200个，因此可以判断起始地点与目的地点之间是否被禁止通行的点所隔离，
那么只有以下两种情况可以隔离：
考虑禁止通行的点数目很少，那么禁止通行的点所能包围的最大面积为与表格的两个边界构成等腰三角形的情况，此时包围的点个数为 n*(n-1)/2；其他情况能包围的最大面积一定小于此。
因此可以从起始地点和目的地点分别进行BFS，判断搜索的最大点是否超过n*(n-1)/2；超过则表示没有被包围，如果起始和目的地点都没有被包围，则表示他们之间可达。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include "vector"
#include "algorithm"
#include "queue"
#include "unordered_map"
using namespace std;
typedef long long LL;
const LL upBound = 1e6;
class Solution {
public:
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
bool isEscapePossible(vector<vector<int>> &blocked, vector<int> &source, vector<int> &target) {
unordered_map<LL, bool> vis1;
for (auto &x: blocked) {
vis1[x[0] * upBound + x[1]] = true;
}
int n = blocked.size();
n = n * (n - 1) / 2;
if (n == 0) return true;
int ans = dfs(n, vis1, source, target);
if (ans == 1) return true;
if (ans == -1) return false;
ans = dfs(n, vis1, target, source);
if (ans == -1) return false;
return true;
}
int dfs(int n, unordered_map<LL, bool> &vis1, vector<int> &source, vector<int> &target) {
unordered_map<LL, bool> vis;
queue<pair<int, int>> que;
que.push(make_pair(source[0], source[1]));
vis[source[0] * upBound + source[1]] = true;
while (!que.empty() && n > 0) {
pair<int, int> pa = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
int sx = pa.first + dx[i];
int sy = pa.second + dy[i];
if (sx == target[0] && sy == target[1]) return 1;
if (sx >= 0 && sy >= 0 && sx < upBound && sy < upBound && !vis[sx * upBound + sy] &&
!vis1[sx * upBound + sy]) {
n--;
if (n == 0) return 0;
vis[sx * upBound + sy] = true;
que.push(make_pair(sx, sy));
}
}
}
if (n <= 0) return 0;
return -1;
}
}; }
if (n <= 0) return 0;
return -1;
}
};
|