Karteikarten
Ohne Titel
Karten in diesem Stapel (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
Informationen
- Beschreibung
- Karteikarten am Ohne Titel, erstellt von Farzana Haque am 16/12/2020.
- Erstellt von
- Farzana Haque
- Aufrufe
- 0
- Bewertung