[Swift]LeetCode286.墙和门$WallsandGates

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

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

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

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

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

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

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 2³¹ - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

您将得到一个由这三个可能值初始化的m x n 2d网格。

-1 - 墙或障碍物。
0 - 门.
INF - 无限意味着一个空房间。我们使用值2^31-1=2147483647表示inf，因为您可以假定到门的距离小于2147483647。
把每个空房间填满到最近的门的距离。如果不可能到达一个门，应该用inf填充。

把每个空房间填满到最近的门的距离。如果不可能到达一个门，应该用inf填充。

例如，给定二维网格：

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

运行函数后，二维网格应为：

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Solution:BFS (Time Limit Exceeded)

 1 class Solution {
 2     func wallsAndGates(_ rooms:inout [[Int]]) {
 3         var q:[(Int,Int)] = [(Int,Int)]()
 4         var dirs:[[Int]] = [[0, -1],[-1, 0],[0, 1],[1, 0]]
 5         for i in 0..<rooms.count
 6         {
 7             for j in 0..<rooms[i].count
 8             {
 9                 if rooms[i][j] == 0
10                 {
11                     q.append((i, j))
12                 }
13             }
14         }
15         while(!q.isEmpty)
16         {
17             let i:Int = q.first!.0
18             let j:Int = q.first!.1
19             q.popLast()
20             for k in 0..<dirs.count
21             {
22                 let x:Int = i + dirs[k][0]
23                 let y:Int = j + dirs[k][1]
24                 if x < 0 || x >= rooms.count || y < 0 || y >= rooms[0].count || rooms[x][y] < rooms[i][j] + 1
25                 {
26                     continue
27                 }
28                 rooms[x][y] = rooms[i][j] + 1
29                 q.append((x, y))
30             }
31         }
32     }
33 }

Solution:DFS (严重超时产生错误)

 1 class Solution {
 2     func wallsAndGates(_ rooms:inout [[Int]]) {
 3         for i in 0..<rooms.count
 4         {
 5             for j in 0..<rooms[i].count
 6             {
 7                 if rooms[i][j] == 0
 8                 {
 9                     dfs(&rooms, i, j, 0)
10                 }
11             }
12         }
13     }
14     
15     func dfs(_ rooms:inout [[Int]],_ i:Int,_ j:Int,_ val:Int)
16     {
17         if i < 0 || i >= rooms.count || j < 0 || j >= rooms[i].count || rooms[i][j] < val
18         {
19             return
20         }
21         dfs(&rooms, i + 1, j, val + 1)
22         dfs(&rooms, i - 1, j, val + 1)
23         dfs(&rooms, i, j + 1, val + 1)
24         dfs(&rooms, i, j - 1, val + 1)
25     }
26 }

点击：Playground测试

1 var sol = Solution()
2 let num:Int = Int(Int32.max - 1)
3 var arr:[[Int]] = [[num,-1,0,num],[num,num,num,-1],[num,-1,num,-1],[0,-1,num,num]]
4 sol.wallsAndGates(&arr)
5 print(arr)
6 //Print