[Swift]LeetCode1036.逃离大迷宫|EscapeaLargeMaze

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

Input: blocked = [0,2]
Output: false
Explanation: 
The target square is inaccessible starting from the source square, because we can't walk outside the grid.

Example 2:

Input: blocked = [999999,999999]
Output: true
Explanation: 
Because there are no blocked cells, it's possible to reach the target square.

Note:

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

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

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

只有在可以通过一系列的移动到达目标方格时才返回 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 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target

Runtime: 3096 ms

Memory Usage: 24.7 MB

 1 class Solution {
 2     func isEscapePossible(_ blocked: [[Int]], _ source: [Int], _ target: [Int]) -> Bool {
 3         var set:Set<Int> = Set<Int>()
 4         for b in blocked
 5         {
 6             set.insert(b[0]<<32|b[1])
 7             if set.contains(source[0]<<32|source[1]) {return false}
 8             if set.contains(target[0]<<32|target[1]) {return false}
 9         }
10         
11         var ss:[[Bool]] = go(source[0], source[1], set)
12         var ts:[[Bool]] = go(target[0], target[1], set)
13         if abs(source[0] - target[0]) > 200 || abs(source[1] - target[1]) > 200
14         {
15             var pt:Int  = 0
16             for i in 0..<411
17             {
18                 for j in 0..<411
19                 {
20                     if i == 0 || j == 0 || i == 410 || j == 410
21                     {
22                         if ss[i][j] {pt |= 1}
23                         if ts[i][j] {pt |= 2}
24                     }
25                 }
26             }
27             return pt == 3
28         }
29         else
30         {
31             return ss[target[0]-source[0]+205][target[1]-source[1]+205]
32         }
33     }
34     
35     func go(_ sr:Int,_ sc:Int,_ obs:Set<Int>) -> [[Bool]]
36     {
37         var can:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: 411), count: 411)
38         can[205][205] = true
39         var q:[[Int]] = [[Int]]()
40         q.append([205, 205])
41         let dr:[Int] = [ 1, 0, -1, 0 ]
42         let dc:[Int] = [ 0, 1, 0, -1 ]
43         while(!q.isEmpty)
44         {
45             var cur:[Int] = q.removeLast()
46             let r:Int = cur[0]
47             let c:Int = cur[1]
48             for k in 0..<4
49             {
50                 let nr:Int = r + dr[k]
51                 let nc:Int = c + dc[k]
52                 if nr >= 0 && nr < 411 && nc >= 0 && nc < 411 && !can[nr][nc]
53                     && sr-205+nr >= 0 && sr-205+nr < 1000000
54                     && sc-205+nc >= 0 && sc-205+nc < 1000000
55                     && !obs.contains((sr-205+nr)<<32|(sc-205+nc))
56                 {
57                     can[nr][nc] = true
58                     q.append([nr, nc])
59                 }
60             }
61         }
62         return can
63     }
64 }