今天在做题的时候，遇到一个BFS，第一反应还是队列，结果玄而又玄的过了，看了下其他人的代码，发现快的全是用list做的。

差很多的那种，看情况也不是因为leetcode判题时间随机的样子。

传送门 地图分析

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

示例：

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

提示：

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] 不是 0 就是 1

 

很简单的BFS，从陆地开始搜索就行了。

使用队列 ：  1548 ms   两倍，弹出队列造成的？

import queue

class Solution:
    def maxDistance(self, grid) -> int:
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]

        n = len(grid)
        q = queue.Queue()
        vis = dict()

        max_dis = -1
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q.put([i, j, 0])
                    vis[(i, j)] = 0

        while not q.empty():
            x, y, cnt = q.get()
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]
                if 0 <= tx < n and 0 <= ty < n and (tx, ty) not in vis:
                    max_dis = max(max_dis, cnt + 1)
                    vis[(tx, ty)] = cnt + 1
                    q.put([tx, ty, cnt + 1])
        return max_dis

 

使用list：  时间是 712 ms

import queue

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        
        n = len(grid)
        q = list()
        vis = dict()
        
        max_dis = -1
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append([i,j,0])
                    vis[(i,j)] = 0
        
        if len(q) == 0:
            return -1
        
        while len(vis) < n*n:
            tmp = []
            for x,y,cnt in q:    
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    if 0 <= tx < n and 0 <= ty < n and (tx,ty) not in vis:
                        max_dis = max(max_dis, cnt+1)
                        vis[(tx,ty)] = cnt + 1
                        tmp.append([tx, ty, cnt+1])
            q = tmp.copy()
        return max_dis