Adanın çevresi
Görev tanımı
Problem
Bir grid kara için 1, su için 0 tutuyor ve bütün kara, içinde göl olmayan tek bir bağlı ada oluşturuyor. Adanın kıyı şeridinin uzunluğunu ölç; suya ya da grid'in kenarına değen her hücre kenarı için bir birim say.
Örnekler
Input: grid = [[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]]
Output: 16
Input: grid = [[1, 1],
[1, 1]]
Output: 8
Neden: dört hücrelik dolu bir karenin açıkta sekiz kenarı var
Input: grid = [[1]]
Output: 4
Neden: edge case: yalnız bir hücre her kenarından açıkta
İpuçları
0 / 3
Kıyıyı sırayla dolaşmak zorunda değilsin. Kıyı şeridinin her birimi tam olarak bir kara hücresine aittir, yani hücreler herhangi bir sırayla ziyaret edilebilir.
Tek bir kara hücresine bak ve dört kenarından hangilerinin kara olmayan bir şeye baktığını sor.
Bütün grid'i tara. Her kara hücresi için dört komşu konumu kontrol et ve grid'in dışında olan ya da su olan her komşu için bir ekle. Kümülatif toplam çevredir.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(1)
Kısıtlar
- cells are 1 (land) or 0 (water)
- the land forms one connected island with no lakes
Çözüm
Kıyı şeridinin her birimi bir kara hücresinin bir kenarıdır; bu yüzden çevre bir döngü olarak izlenmek yerine hücre hücre toplanabilir. Bir kenar, o yöndeki komşu su olduğunda ya da tamamen grid'in dışına düştüğünde sayılır; bu, sınır testi içine katlanmış aynı kontroldür. Bu da her şeyi hücre başına dört yoklama ve hiçbir dolaşma durumu olmayan düz bir taramaya çevirir. Zaman O(rows * cols), alan O(1).
def perimeter(g):
rows, cols, total = len(g), len(g[0]), 0
for r in range(rows):
for c in range(cols):
if g[r][c] != 1:
continue
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
off = not (0 <= nr < rows and 0 <= nc < cols)
if off or g[nr][nc] == 0: # that side faces water or the edge
total += 1
return total
print(perimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]])) # -> 16
print(perimeter([[1, 1], [1, 1]])) # -> 8
print(perimeter([[1]])) # -> 4Kodda değil de fikirde mi takıldın? Grid'de dolaşma bunu anlatıyor.