客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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:
For example, given three buildings at 1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 The point Note: 你想在一片空旷的土地上建造一座房子，它能在最短的距离内到达所有的建筑物。你只能上下左右移动。您将得到一个值为0、1或2的二维网格，其中： 每0分代表一片空地，你可以自由通行。 每1个标记一个不能穿过的建筑物。 每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.count 10 { 11 for j in 0..<grid[i].count 12 { 13 if grid[i][j] == 1 14 { 15 res = Int.max 16 var dist:[[Int]] = grid 17 var q:[(Int,Int)] = [(Int,Int)]() 18 q.append((i, j)) 19 while(!q.isEmpty) 20 { 21 var a:Int = q.first!.0 22 var b:Int = q.first!.1 23 q.removeFirst() 24 for k in 0..<dirs.count 25 { 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] == val 29 { 30 grid[x][y] -= 1 31 dist[x][y] = dist[a][b] + 1 32 sum[x][y] += (dist[x][y] - 1) 33 q.append((x, y)) 34 res = min(res, sum[x][y]) 35 } 36 } 37 } 38 val -= 1 39 } 40 } 41 } 42 return res == Int.max ? -1 : res 43 } 44 } 点击：Playground测试 1 var arr:[[Int]] = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] 2 var sol = Solution() 3 print(sol.shortestDistance(&arr)) 4 //Print 7
|
请发表评论