題目鏈接
難度：中等 ??????類型： 廣度優(yōu)先搜索

你現(xiàn)在手里有一份大小為 N x N 的『地圖』（網(wǎng)格） grid，上面的每個(gè)『區(qū)域』（單元格）都用 0 和 1 標(biāo)記好了。其中 0 代表海洋，1 代表陸地，你知道距離陸地區(qū)域最遠(yuǎn)的海洋區(qū)域是是哪一個(gè)嗎？請(qǐng)返回該海洋區(qū)域到離它最近的陸地區(qū)域的距離。

我們這里說的距離是『曼哈頓距離』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 這兩個(gè)區(qū)域之間的距離是 |x0 - x1| + |y0 - y1| 。

如果我們的地圖上只有陸地或者海洋，請(qǐng)返回 -1。

示例1

輸入：[[1,0,1],[0,0,0],[1,0,1]]
輸出：2
解釋：
海洋區(qū)域 (1, 1) 和所有陸地區(qū)域之間的距離都達(dá)到最大，最大距離為 2。

示例2

輸入：[[1,0,0],[0,0,0],[0,0,0]]
輸出：4
解釋：
海洋區(qū)域 (2, 2) 和所有陸地區(qū)域之間的距離都達(dá)到最大，最大距離為 4。

解題思路

1. 先找到grid中所有的1的位置，保存在queue中，若全是1或者沒有1，返回-1
2. 從這些1所在的位置開始進(jìn)行廣度優(yōu)先搜索，即搜索四個(gè)方向，如果搜索的位置上的值為0，保存這些坐標(biāo)，作為下一次搜索的起點(diǎn)，并將這些位置的值設(shè)置為1，以免重復(fù)搜索。這樣每擴(kuò)散一層，計(jì)數(shù)器加1，直到?jīng)]有可搜索的起點(diǎn)，返回計(jì)數(shù)器的值就為最遠(yuǎn)的距離

代碼實(shí)現(xiàn)

class Solution(object):
     def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        queue = [(i,j) for i in range(n) for j in range(n) if grid[i][j] == 1]
        if len(queue) == n * n or not queue: return -1
        level = 0
        while queue:
            t = []
            for x,y in queue:
                for i,j in [(x+1,y), (x-1, y), (x, y+1), (x, y-1)]:
                    if 0 <= i < n and 0 <= j < n and grid[i][j] == 0:
                        t.append((i, j))
                        grid[i][j] = 1
            queue = t
            level += 1
        return level-1

本文鏈接：http://www.itdecent.cn/p/ea5c190f412f