[Swift]LeetCode864.获取所有钥匙的最短路径|ShortestPathtoGetAllKeys

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

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

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

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

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

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

We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can't walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first Kletters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it's impossible, return -1.

Example 1:

Input: 8

Example 2:

Input: 6

Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only'.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.

给定一个二维网格 grid。 "." 代表一个空房间， "#" 代表一堵墙， "@" 是起点，（"a", "b", ...）代表钥匙，（"A", "B", ...）代表锁。

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 K 为钥匙/锁的个数，且满足 1 <= K <= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

输入：["@.a.#","###.#","b.A.B"]
输出：8

示例 2：

输入：["@..aA","..B#.","....b"]
输出：6

提示：

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
钥匙的数目范围是 [1, 6]，每个钥匙都对应一个不同的字母，正好打开一个对应的锁。

Runtime: 532 ms

Memory Usage: 20.5 MB

  1 class Solution {
  2     func shortestPathAllKeys(_ grid: [String]) -> Int {
  3         var x:Int = -1
  4         var y:Int = -1
  5         var m:Int = grid.count
  6         var n:Int = grid[0].count
  7         var maxNum:Int = -1
  8         for i in 0..<m
  9         {
 10             for j in 0..<n
 11             {
 12                 var c:Character = grid[i][j]
 13                 if c == "@"
 14                 {
 15                     x = i
 16                     y = j
 17                 }
 18                 if c >= "a" && c <= "f"
 19                 {
 20                     maxNum = max(c.ascii - 97 + 1, maxNum)
 21                 }
 22             }
 23         }
 24         var start:State = State(0, x, y)
 25         var q:[State] = [State]()
 26         var visited:Set<String> = Set<String>()
 27         visited.insert(String(0) + " " + String(x) + " " + String(y))
 28         q.append(start)
 29         var dirs:[[Int]] = [[0, 1],[1, 0],[0, -1],[-1, 0]]
 30         var step:Int = 0
 31         while (!q.isEmpty)
 32         {
 33             var size:Int = q.count
 34             while(size-- > 0)
 35             {
 36                 var cur:State = q.removeFirst()
 37                 if cur.keys == ((1 << maxNum) - 1) 
 38                 {
 39                     return step
 40                 }
 41                 for dir in dirs
 42                 {
 43                     var i:Int = cur.i + dir[0]
 44                     var j:Int = cur.j + dir[1]
 45                     var keys:Int = cur.keys
 46                     if i >= 0 && i < m && j >= 0 && j < n
 47                     {
 48                         var c:Character = grid[i][j]
 49                         if c == "#"
 50                         {
 51                             continue
 52                         }
 53                         if c >= "a" && c <= "f"
 54                         {
 55                             keys |= 1 << (c.ascii - 97)
 56                         }
 57                         if c >= "A" && c <= "F" && ((keys >> (c.ascii - 65)) & 1) == 0
 58                         {
 59                             continue
 60                         }
 61                         var str:String = String(keys) + " " + String(i) + " " + String(j)
 62                         if !visited.contains(str)
 63                         {
 64                             visited.insert(str)
 65                             q.append(State(keys, i, j))
 66                         }
 67                     }
 68                 }                
 69             }
 70             step += 1            
 71         }
 72         return -1        
 73     }
 74 }
 75 
 76 class State
 77 {
 78     var keys:Int
 79     var i:Int
 80     var j:Int 
 81     init(_ keys:Int,_ i:Int,_ j:Int)
 82     {
 83         self.keys = keys
 84         self.i = i
 85         self.j = j
 86     }
 87 }
 88 
 89 //String扩展
 90 extension String {        
 91     //subscript函数可以检索数组中的值
 92     //直接按照索引方式截取指定索引的字符
 93     subscript (_ i: Int) -> Character {
 94         //读取字符
 95         get {return self[index(startIndex, offsetBy: i)]}
 96     }
 97 }
 98 
 99 //Character扩展 
100 extension Character  
101 {  
102   //Character转ASCII整数值(定义小写为整数值)
103    var ascii: Int {
104        get {
105            return Int(self.unicodeScalars.first?.value ?? 0)
106        }       
107     }
108 }
109 
110 /*扩展Int类，实现自增++、自减--运算符*/
111 extension Int{
112     //后缀--:先执行表达式后再自减
113     static postfix func --(num:inout Int) -> Int {
114         //输入输出参数num
115         let temp = num
116         //num减1
117         num -= 1
118          //返回减1前的数值
119         return temp
120     }
121 }