Avoiding Bears

Meta Interview

Given a grid, with walls and bears in it, return the safest place from all the bears

首先需要clarify safest，safest place would be the place with the largest shortest distance from all the bears

直觉上的想法是从每个bear出发得到每个点到每个bear的距离，然后找出它们中最小值最大的格子

但是其实可以从所有bear同时出发做多源bfs，可以一次性得到每个格子到最近bear的距离，也就是到所有bear的最小值。如果之后从另一个bear出发又遇到那么一定没有先遇上的bear近。

'''
grid: 0 for cells, 1 for walls, 2 for bears
what is the safest spot from bear?
'''
from collections import deque

DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def SafestFromBears(grid):
    if not grid or len(grid)==0 or len(grid[0])==0:
        return []
    
    q = deque()
    visited = set()
    for i in range(grid):
        for j in range(grid[0]):
            if grid[i][j] == 2:
                q.append((i, j))
                visited.add((i, j))
    distance = 0 
    ans = []      
    while q:
        l = len(q)
        ans = []
        for _ in range(l):
            i, j = q.popleft()
            ans.append((i, j))
            for dx, dy in DIR:
                ni = i+dx
                nj = j+dy
                if is_valid(ni, nj, grid, visited):
                    q.append((ni, nj))
                    visited.add((ni, nj))
        distance += 1  

    return ans

def is_valid(i, j, grid, visited) -> bool:
    m = len(grid)
    n = len(grid[0])

    if i < 0 or i >= m or j < 0 or j >= n:
        return False
    
    if grid[i][j] != 0:
        return False
    
    return (i, j) not in visited
```