En büyük ada alanı
Görev tanımı
Problem
Bir harita 0'lardan (su) ve 1'lerden (kara) oluşan bir grid. Bir ada yukarı, aşağı, sola ya da sağa bağlı kara hücrelerinden oluşan bir gruptur; çapraz komşular bağlanmaz. Bir adanın alanı hücre sayısıdır. En büyük adanın alanını döndür; hiç kara yoksa 0 döndür.
Örnekler
Input: grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]]
Output: 4
Neden: sol üstteki adanın 3, sağdakinin 4 hücresi var
Input: grid = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Output: 1
Neden: çapraz hücreler birleşmez, bu yüzden tek hücrelik beş ada var
Input: grid = [[0, 0], [0, 0]]
Output: 0
Neden: edge case: hiç kara yok
İpuçları
0 / 3
Bu, tek bir değişiklikle ada sayma: kaç ada başlattığını saymak yerine her birini keşfederken ölç.
Her hücreyi tara. Karaya rastladığında bütün adayı oradan bir stack ya da kuyrukla keşfet ve ziyaret ettiğin hücreleri say.
Bir hücreyi push ettiğin anda ziyaret edildi olarak işaretle, örneğin onu 0 yaparak; böylece asla iki kez sayılmaz ve asla ikinci bir arama başlatmaz. En büyük sayıyı tut.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(rows · cols)
Kısıtlar
- cells are 1 (land) or 0 (water)
Çözüm
Her kara hücresi tam olarak bir adaya aittir ve herhangi bir hücresinden başlayan bir flood fill bütün adayı ve başka hiçbir şeyi ziyaret etmez. Dış tarama yalnız henüz ziyaret edilmemiş karada bir doldurma başlatır, doldurma da hücreleri pop ettikçe sayar. Bir hücreyi push edilir edilmez batırmak (0 yapmak) ziyaret işaretidir; böylece hiçbir hücre iki kez push edilmez. Açık bir stack büyük bir adanın Python'un özyineleme (recursion) sınırına takılmasını engeller. Her hücre bir kez taranır ve en fazla bir kez push edilir; zaman O(rows × cols), stack en kötü durumda O(rows × cols) hücre tutabilir. Fonksiyon bir kopya üzerinde çalışır, böylece çağıranın grid'i dokunulmadan kalır.
def largest_island(grid):
grid = [row[:] for row in grid] # sink cells in a copy
rows, cols = len(grid), len(grid[0])
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
grid[r][c] = 0
stack, area = [(r, c)], 0
while stack:
y, x = stack.pop()
area += 1
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == 1:
grid[ny][nx] = 0 # visited the moment it is pushed
stack.append((ny, nx))
best = max(best, area)
return best
print(largest_island([[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]])) # -> 4
print(largest_island([[1, 0, 1], [0, 1, 0], [1, 0, 1]])) # -> 1
print(largest_island([[0, 0], [0, 0]])) # -> 0Kodda değil de fikirde mi takıldın? Number of Islands bunu anlatıyor.