[Swift]LeetCode317. 建筑物的最短距离 $ Shortest Distance from All Buildings

概述You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, wher

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up,down,left and right. You are given a 2D grID of values 0, 1 or 2,where:

Each 0 marks an empty land which you can pass by freely. Each 1 marks a building which you cannot pass through. Each 2 marks an obstacle which you cannot pass through.

For example,given three buildings at (0,0), (0,4), (2,2),and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1|   |   |   |   |0 - 0 - 0 - 0 - 0|   |   |   |   |0 - 0 - 1 - 0 - 0

The point (1,2) is an IDeal empty land to build a house,as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules,return -1.

你想在一片空旷的土地上建造一座房子，它能在最短的距离内到达所有的建筑物。你只能上下左右移动。您将得到一个值为0、1或2的二维网格，其中：

每0分代表一片空地，你可以自由通行。

每1个标记一个不能穿过的建筑物。

每2个标记一个你不能通过的障碍物。

例如，假设(0,2)处有三座建筑物，而(0,2)处有障碍物：

1 - 0 - 2 - 0 - 1|   |   |   |   |0 - 0 - 0 - 0 - 0|   |   |   |   |0 - 0 - 1 - 0 - 0

由于3+3+1=7的总行程最小，因此点(1,2)是建造房屋的理想空地。所以返回7。

注：

至少有一栋楼。如果无法按照上述规则建造此类房屋，则返回-1。

Solution:

 1 class Solution { 2     func shortestdistance(_ grID:inout [[Int]]) -> Int { 3         var res:Int = Int.max 4         var val:Int = 0 5         var m:Int = grID.count 6         var n:Int = grID[0].count 7         var sum:[[Int]] = grID 8         var dirs:[[Int]] = [[0,-1],[-1,0],[0,1],[1,0]] 9         for i in 0..<grID.count10         {11             for j in 0..<grID[i].count12             {13                 if grID[i][j] == 114                 {15                     res = Int.max16                     var dist:[[Int]] = grID17                     var q:[(Int,Int)] = [(Int,Int)]()18                     q.append((i,j))19                     while(!q.isEmpty)20                     {21                         var a:Int = q.first!.022                         var b:Int = q.first!.123                         q.removeFirst()24                         for k in 0..<dirs.count25                         {26                             var x:Int = a + dirs[k][0]27                             var y:Int = b + dirs[k][1]28                             if x >= 0 && x < m && y >= 0 && y < n && grID[x][y] == val29                             {30                                 grID[x][y] -= 131                                 dist[x][y] = dist[a][b] + 132                                 sum[x][y] += (dist[x][y] - 1)33                                 q.append((x,y))34                                 res = min(res,sum[x][y])35                             }36                         }37                     }38                     val -= 139                 }40             }41         }42         return res == Int.max ? -1 : res    43     }44 }

点击：Playground测试

1 var arr:[[Int]] = [[1,0,2,1,0]]2 var sol = Solution()3 print(sol.shortestdistance(&arr))4 //Print 7

总结

以上是内存溢出为你收集整理的[Swift]LeetCode317. 建筑物的最短距离 $ Shortest Distance from All Buildings全部内容，希望文章能够帮你解决[Swift]LeetCode317. 建筑物的最短距离 $ Shortest Distance from All Buildings所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。