Flashcards
Sem título
Flashcards do conjunto (1)
- 1Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
if not grid:
return 0
row_size = len(grid)
col_size = len(grid[0])
moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
house = deque()
total = 0
dis_to_near_house = defaultdict(list)
for r in range(row_size):
for c in range(col_size):
if grid[r][c] == 1:
house.append([r, c, 0])
total += 1
def get_distance(start):
q = deque([start])
seen = set()
while q:
r, c, l = q.popleft()
for x, y in moves:
new_x, new_y = r+x, y+c
valid = 0<= new_x
Informações
- Descrição
- FlashCards sobre Sem título, criado por Farzana Haque em 16-12-2020.
- Criado por
- Farzana Haque
- Visualizações
- 0
- Avaliação