Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个0-1格子地图,1表示陆地,0表示水,问距离陆地最远的水的距离(曼哈顿距离)多少
先找出所有1的格子,然后BFS所有0的格子,每次把上一步所有压进队列的格子全部更新一遍,直到所有为0的格子走完


#1162
#
Runtime: 512 ms (Beats 76.36%)
#
Memory: 15.2 MB (Beats 27.27%)

class Solution(object):
    def maxDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        
"""
        ans = -1
        n = len(grid)
        d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        q = deque()
        vis = set()
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append([i, j])
        if not q or len(q) == n**2:
            return -1
        while q:
            ans += 1
            sz = len(q)
            while sz:
                sz -= 1
                x, y = q.popleft()
                for dx, dy in d:
                    xx = x + dx
                    yy = y + dy
                    if 0 <= xx < n and 0 <= yy < n and xx * n + yy not in vis and grid[xx][yy] == 0:
                        vis.add(xx * n + yy)
                        q.append([xx, yy])
        return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理