• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. 0 <= blocked.length <= 200
  2. blocked[i].length == 2
  3. 0 <= blocked[i][j] < 10^6
  4. source.length == target.length == 2
  5. 0 <= source[i][j], target[i][j] < 10^6
  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
解释:
因为没有方格被封锁,所以一定可以到达目标方格。

提示:

  1. 0 <= blocked.length <= 200
  2. blocked[i].length == 2
  3. 0 <= blocked[i][j] < 10^6
  4. source.length == target.length == 2
  5. 0 <= source[i][j], target[i][j] < 10^6
  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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap