突破封锁线

发表于 更新于 分类于 ，

简介

在一个\(10^6 * 10^6\)​​ 的网格中，每个网格上方格的坐标为 (x, y)。

现在从源方格 source = [sx, sy]开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi)的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

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

(Leet1036)

  • 示例 1：
1
2
3
4
5
6
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。
  • 示例 2：
1
2
3
4
输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。
  • 数据量：
    • 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进行暴力搜索，采用双向BFS来进行优化：

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
class Solution:
    def isEscapePossible(self, blocked, source, target) -> bool:
        m = 10 ** 6
        hashBlock = dict(map(lambda x: [tuple(x), 0], blocked))
        queue_s = [tuple(source)]
        queue_t = [tuple(target)]
        hashPoint_s = dict()
        hashPoint_t = dict()
        hashPoint_s[tuple(source)] = 0
        hashPoint_t[tuple(target)] = 0
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue_s != [] and queue_t != []:
            len_s = len(queue_s)
            len_t = len(queue_t)
            if len_s < len_t:
                for i in range(len_s):
                    point = queue_s.pop(0)
                    for d in direct:
                        new_point = (point[0] + d[0], point[1] + d[1])
                        if new_point[0] < 0 or new_point[0] >= m or new_point[1] < 0 or new_point[1] >= m:
                            continue
                        if new_point in hashBlock:
                            continue
                        if new_point in hashPoint_s:
                            continue
                        if new_point in hashPoint_t:
                            return True
                        queue_s.append(new_point)
                        hashPoint_s[new_point] = 0
            else:
                for i in range(len_t):
                    point = queue_t.pop(0)
                    for d in direct:
                        new_point = (point[0] + d[0], point[1] + d[1])
                        if new_point[0] < 0 or new_point[0] >= m or new_point[1] < 0 or new_point[1] >= m:
                            continue
                        if new_point in hashBlock:
                            continue
                        if new_point in hashPoint_t:
                            continue
                        if new_point in hashPoint_s:
                            return True
                        queue_t.append(new_point)
                        hashPoint_t[new_point] = 0
        return False

但是此题数据量较大，使用这样的方式肯定会超时，寻找进一步优化。

此题最终要求解的是能不能突破封锁，不需要求路劲问题，可以进行剪枝。具体做法是：求出所给的封锁点所能够封锁的的总数据点的数量，双向BFS的时候，若最小的一方遍历到的路径点大于所能封锁的最大点的数量，则说明题中所给的封锁点不能封锁所有的路径，直接返回True即可。所给点能封锁的最大点数量可以使用公式\(n*(n-1)/2\)​​计算，此时包围情况为封锁线与边界成等腰直角三角形的情形，下图是11个封锁点所能封锁的最大点数量：

image-20210917150841216
image-20210917150841216

$$ maxpoints=1+2+...+10== \(​​​\)

剪枝后的BFS算法：

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
class Solution:
    def isEscapePossible(self, blocked, source, target) -> bool:
        m = 10 ** 6
        hashBlock = dict(map(lambda x: [tuple(x), 0], blocked))
        n = len(hashBlock)
        n = n*(n-1)//2  # 计算可封锁的点的最大数量
        queue_s = [tuple(source)]
        queue_t = [tuple(target)]
        hashPoint_s = dict()
        hashPoint_t = dict()
        hashPoint_s[tuple(source)] = 0
        hashPoint_t[tuple(target)] = 0
        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue_s != [] and queue_t != []:
            len_s = len(queue_s)
            len_t = len(queue_t)
            if min(len(hashPoint_s),len(hashPoint_t))>n: # 判断是否可以冲破封锁
                return True
            if len_s < len_t:
                for i in range(len_s):
                    point = queue_s.pop(0)
                    for d in direct:
                        new_point = (point[0] + d[0], point[1] + d[1])
                        if new_point[0] < 0 or new_point[0] >= m or new_point[1] < 0 or new_point[1] >= m:
                            continue
                        if new_point in hashBlock:
                            continue
                        if new_point in hashPoint_s:
                            continue
                        if new_point in hashPoint_t:
                            return True
                        queue_s.append(new_point)
                        hashPoint_s[new_point] = 0
            else:
                for i in range(len_t):
                    point = queue_t.pop(0)
                    for d in direct:
                        new_point = (point[0] + d[0], point[1] + d[1])
                        if new_point[0] < 0 or new_point[0] >= m or new_point[1] < 0 or new_point[1] >= m:
                            continue
                        if new_point in hashBlock:
                            continue
                        if new_point in hashPoint_t:
                            continue
                        if new_point in hashPoint_s:
                            return True
                        queue_t.append(new_point)
                        hashPoint_t[new_point] = 0
        return False