1036：逃离大迷宫（2164 分）

2019-04-28 约 899 字预计阅读 2 分钟次阅读

力扣第 134 场周赛第 4 题

题目

在一个 10⁶ x 10⁶ 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [s_x, s_y] 开始出发，意图赶往目标方格 target = [t_x, t_y] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [x_i, y_i] 表示坐标为 (x_i, y_i) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 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 <= x_i, y_i < 10⁶
source.length == target.length == 2
0 <= s_x, s_y, t_x, t_y < 10⁶
source != target
题目数据保证 source 和 target 不在封锁列表内

分析

#1

容易想到 bfs 找路径
网格很大，障碍物很少，遍历障碍物之间的大片空白太浪费时间
考虑将连续若干个空白行/列压缩成 1 行/列，不影响连通性
压缩后的新图跑 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


class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        def gen(A):
            d = {0:0}
            i = 0
            for a,b in pairwise(A):
                i += min(2,b-a)
                d[b] = i
            return d
        n = 10**6
        (sx,sy),(tx,ty) = source,target
        d1 = gen(sorted({x for x,_ in blocked}|{sx,tx,0,n}))
        d2 = gen(sorted({y for _,y in blocked}|{sy,ty,0,n}))
        m,n = d1[n],d2[n]
        sx,sy,tx,ty = d1[sx],d2[sy],d1[tx],d2[ty]
        vis = {(d1[x],d2[y]) for x,y in blocked}|{(sx,sy)}
        Q = deque([(sx,sy)])
        while Q:
            i,j = Q.popleft()
            if (i,j)==(tx,ty):
                return True
            for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                if 0<=x<m and 0<=y<n and (x,y) not in vis:
                    Q.append((x,y))
                    vis.add((x,y))
        return False

406 ms

#2

还有个更优的做法
随意挑选一条从 source 到 target 的路径
- 最简单的路径就是先水平走到与 target 同一列的位置，再竖直走到 target
如果路径上有障碍物，要么能绕着障碍物走回到路径上的某个位置，要么就不能达到 target
因此，只需要考虑障碍物周围（注意是八个相邻格子）和路径上的格子，基于这些格子 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


class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        def gen(A):
            d = {0:0}
            i = 0
            for a,b in pairwise(A):
                i += min(2,b-a)
                d[b] = i
            return d
        n = 10**6
        (sx,sy),(tx,ty) = source,target
        d1 = gen(sorted({x for x,_ in blocked}|{sx,tx,0,n}))
        d2 = gen(sorted({y for _,y in blocked}|{sy,ty,0,n}))
        m,n = d1[n],d2[n]
        sx,sy,tx,ty = d1[sx],d2[sy],d1[tx],d2[ty]
        B = {(d1[x],d2[y]) for x,y in blocked}
        valid = set()
        for i,j in B:
            for x,y in product(range(i-1,i+2),range(j-1,j+2)):
                if 0<=x<m and 0<=y<n:
                    valid.add((x,y))
        for i in (range(sx,tx+1) if sx<tx else range(tx,sx+1)):
            valid.add((i,sy))
        for j in (range(sy,ty+1) if sy<ty else range(ty,sy+1)):
            valid.add((tx,j)) 
        Q = deque([(sx,sy)])
        B.add((sx,sy))
        while Q:
            i,j = Q.popleft()
            if (i,j)==(tx,ty):
                return True
            for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                if (x,y) in valid and (x,y) not in B:
                    Q.append((x,y))
                    B.add((x,y))
        return False

11 ms

目录

1036：逃离大迷宫（2164 分）

题目

分析

#1

#2

解答