开放原子开发者工作坊

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

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,0), (0,4), (2,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:

class Solution {
    func shortestDistance(_ grid:inout [[Int]]) -> Int {
        var res:Int = Int.max
        var val:Int = 0
        var m:Int = grid.count
        var n:Int = grid[0].count
        var sum:[[Int]] = grid
        var dirs:[[Int]] = [[0,-1],[-1,0],[0,1],[1,0]]
        for i in 0..<grid.count
        {
            for j in 0..<grid[i].count
            {
                if grid[i][j] == 1
                {
                    res = Int.max
                    var dist:[[Int]] = grid
                    var q:[(Int,Int)] = [(Int,Int)]()
                    q.append((i, j))
                    while(!q.isEmpty)
                    {
                        var a:Int = q.first!.0
                        var b:Int = q.first!.1
                        q.removeFirst()
                        for k in 0..<dirs.count
                        {
                            var x:Int = a + dirs[k][0]
                            var y:Int = b + dirs[k][1]
                            if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == val
                            {
                                grid[x][y] -= 1
                                dist[x][y] = dist[a][b] + 1
                                sum[x][y] += (dist[x][y] - 1)
                                q.append((x, y))
                                res = min(res, sum[x][y])
                            }
                        }
                    }
                    val -= 1
                }
            }
        }
        return res == Int.max ? -1 : res    
    }
}

点击：Playground测试

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