【搜索难题】力扣1036-有限BFS,二维离散化

  |  

摘要: 本文详细拆解 leetcode 1036-逃离大迷宫,有带步数上限的 BFS 和二维离散化两种方法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


算法要点:

  • 有限 BFS
  • 二维离散化

$1 题目

题目链接

1036. 逃离大迷宫

题目描述

在一个 10^6 x 10^6 的网格中,每个网格块的坐标为 (x, y),其中 0 <= x, y < 10^6。

我们从源方格 source 开始出发,意图赶往目标方格 target。每次移动,我们都可以走到网格中在四个方向上相邻的方格,只要该方格不在给出的封锁列表 blocked 上。

只有在可以通过一系列的移动到达目标方格时才返回 true。否则,返回 false。

数据范围

1
2
3
4
5
6
0 <= blocked.length <= 200
blocked[i].length == 2
0 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target

样例

示例 1:
输入:blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出:false
解释:
从源方格无法到达目标方格,因为我们无法在网格中移动。

示例 2:
输入:blocked = [], source = [0,0], target = [999999,999999]
输出:true
解释:
因为没有方格被封锁,所以一定可以到达目标方格。

$2 题解

算法1: 有限BFS

类似于这种从网格的中间往外找路的需求,总是先想到 BFS,乍一看网格有 1e6 * 1e6 = 1e12 这么多,简单地BFS 搜索所有格子应该是不行了。

但是仔细一看,BFS 的步数是有上限的,根本不会走到 1e12 这么多。因为如果最终不能从起点到终点,则从起点或终点出发能到达的格子数量不超过 m(m-1)/2。

当 m = 200 时,起点在 (0, 0) 且障碍点以一条斜线封住起点的情况,障碍点可以围住最多的点,(199 + 1) * 199 /2 = 19900。这个数量级就可以了。

先从起点开始 BFS,如果过程中遇到了终点或者可达格子个数超过了 m(m-1)/2,则返回true,否则返回false;同理再从终点走一遍。如果两次都返回 true,则从起点可以到达终点。

unordered_set<pair<int, int>> 维护障碍点集合和已经走过的点集合。需要以自定义结构体重载()的方式定义计算 pair<int, int> 的 hashcode 的方式。

1
2
3
4
5
6
7
8
using PII = pair<int, int>;
struct MyHash {
size_t operator() (const PII& v) const {
return hash<int>()(v.first) ^ hash<int>()(v.second);
}
};
unordered_set<PII, MyHash> block;
unordered_set<PII, MyHash> ;

代码

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
using PII = pair<int, int>;
struct MyHash {
size_t operator() (const PII& v) const {
return hash<int>()(v.first) ^ hash<int>()(v.second);
}
};

class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_set<PII, MyHash> block;
for(vector<int> &b: blocked) block.insert({b[0], b[1]});
return bfs(block, source, target) && bfs(block, target, source);
}

private:
bool bfs(unordered_set<PII, MyHash>& blocked, vector<int>& source, vector<int>& target)
{
int n = 1000000, m = 1000000;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
unordered_set<vector<int>, MyHash> visited;
queue<PII> q;
int max_step = blocked.size() * (blocked.size() - 1) / 2;
q.push({source[0], source[1]});
visited.insert({source[0], source[1]});
int step = 1;
while(!q.empty())
{
PII cur = q.front();
q.pop();
if(step > max_step)
return true;
for(int d = 0; d < 4; ++d)
{
int x = cur.first + dx[d], y = cur.second + dy[d];
if(x == target[0] && y == target[1])
return true;
if(_check(x, y, n, m) && visited.find({x, y}) == visited.end()
&& blocked.find({x, y}) == blocked.end())
{
q.push({x, y});
visited.insert({x, y});
++step;
}
}
}
return false;
}

bool _check(int i, int j, int n, int m)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
};

算法2: 二维离散化

离散化的核心思想是将数据分布范围大但数量少(即稀疏)的数据进行集中化的处理,减少空间复杂度。

一维离散化的主要应用之一是在用权值树状数组或者权值线段树做区间内的统计时,数组下标是权值,数组的值是权值的计数。因为权值的范围可能会很大且有可能有负数和小数,例如[-1e9, 1e9],开不出这么大的数组。而统计过程只关心元素大小关系,不关心元素的具体的值,并且这么大的数据范围里有出现过的权(最终计数>1的权)很少,因此可以使用离散化的方法把出现过的权按照大小关系映射到[0,1,2,…],这样既保持了元素的大小关系,又可以把权当做数组下标使用了。

本题的情况一样,网格大小是[-1e6, 1e6],但是障碍物只有很少

1
0 <= blocked.length <= 200

所有对结果有影响的只有开始结束点所在的行列,以及每个障碍物所在的行列,他们相邻的行列,把大迷宫转成小迷宫,然后再寻路。

例如一个 16*16 的网格,有5个障碍点(6, 0), (11, 4), (5, 8), (3, 9), (10, 14)。

对结果有影响的行如下(未去重)

1
2
3
起点终点所在行 i = {0, 15};
障碍点所在行 i = {3, 5, 6, 10, 11};
障碍点所在行的相邻) i = {2, 4, 4, 6, 5, 7, 9, 11, 10,12}

对结果有影响的列如下(未去重)

1
2
3
起点终点所在列 j = {0, 15}
障碍点所在列 j = {0, 4, 8, 9, 14}
障碍点所在列的响铃列 j = {1, 3, 5, 7, 9, 8, 10, 13, 15}

分别对这些对结果有影响的行和列做离散化,得到一个较小 12 * 12 的网格

二维离散化之后,原来的起点和终点(0,0), (15, 15) 变成了(0, 0), (12, 12);原有的5个障碍点也有相应的变化

1
2
3
4
5
(6,0) -> (5,0)
(11,4) -> (9,3)
(5,8) -> (4,6)
(3,9) -> (2,7)
(10,14) -> (9,11)

新网格的规模缩小,可以开的出网格规模的数组了,起点,终点,障碍点,障碍点的相邻点的位置关系保持不变。在新网格上对起点和终点的寻路问题可做。

二维离散化的过程

1
2
3
4
5
6
7
8
9
1. 开两个空的vector,x 和 y,分别记录对结果有影响的横坐标,纵坐标
2. 开两个哈希表 setx, set_y, 分别记录已经压进 x, y 的值
3. 枚举所有障碍点、起点、终点 (i, j)
1) 枚举 i - 1(若 i > 0), i, i + 1(若 i < n - 1) , 若未在 set_y 中(未压进x过),则压进 x 并插入 set_x
2) 枚举 j - 1(若 j > 0), j, j + 1(若 i < m - 1) , 若未在 set_y 中(未压进y过),则压进 y 并插入 set_y
4. 对 x, y 分别做一维离散化的排序,去重
5. 开出离散化后的网格 vector<vector<int> > new_grid
6. 确定网格 new_grid 中的起点,终点坐标
7. 离散化后的障碍点记录到 new_grid

二维离散化的另一个经典问题:200. 岛屿数量。本题不做二维离散化,直接BFS找连通分量,或者直接上并查集都可以过。但是如果 Follow up 问如果网格非常非常大,则还是需要先做二维离散化,只保留对结果有影响的点。具体什么样的点是对结果有影响的需要画图具体分析。

代码(C++)

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
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
// 二维离散化
vector<int> x, y;
unordered_set<int> set_x, set_y;
int left = 0, up = 0, right = 1000000 - 1, down = 1000000 - 1;
blocked.push_back(source);
blocked.push_back(target);
for(const vector<int> block: blocked)
{
int i = block[0], j = block[1];
for(int k = i - 1; k <= i + 1; ++k)
{
if(k < up || k > down) continue;
if(set_x.find(k) == set_x.end())
{
x.push_back(k);
set_x.insert(k);
}
}
for(int k = j - 1; k <= j + 1; ++k)
{
if(k < left || k > right) continue;
if(set_y.find(k) == set_y.end())
{
y.push_back(k);
set_y.insert(k);
}
}
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
x.erase(unique(x.begin(), x.end()), x.end());
y.erase(unique(y.begin(), y.end()), y.end());
int n = x.size(), m = y.size();
vector<vector<int> > grid(n, vector<int>(m, 0));
for(const vector<int> block: blocked)
{
int i = block[0], j = block[1];
int new_i = _find(i, x);
int new_j = _find(j, y);
grid[new_i][new_j] = 1;
}
// 在离散化后的网格上对起点终点进行BFS寻路
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<vector<bool> > visited(n, vector<bool>(m, false));
queue<vector<int> > q;
int s_x = _find(source[0], x), s_y = _find(source[1], y);
int e_x = _find(target[0], x), e_y = _find(target[1], y);
q.push(vector<int>({s_x, s_y}));
visited[0][0] = true;
while(!q.empty())
{
vector<int> cur = q.front();
q.pop();
for(int d = 0; d < 4; ++d)
{
int xx = cur[0] + dx[d], yy = cur[1] + dy[d];
if(xx == e_x && yy == e_y)
return true;
if(_check(xx, yy, n, m) && grid[xx][yy] == 0 && !visited[xx][yy])
{
q.push(vector<int>({xx, yy}));
visited[xx][yy] = true;
}
}
}
return false;
}

private:
int _find(int v, const vector<int>& x)
{
return lower_bound(x.begin(), x.end(), v) - x.begin();
}

bool _check(int i, int j, int n, int m)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
};

Share