الجزر في الشبكة: الجيران والحدود

طريقان إلى نفس الفكرة

قبل أن تبدأ

الفكرة الجوهرية

1الجيران والحدود

اكتب الاتجاهات الأربعة في قائمة، وتحقّق من الحدود قبل قراءة أي خانة. هذا يعدّ جيران كل خانة يابسة:

grid = [[0, 1, 0],
        [1, 1, 1],
        [0, 1, 0]]
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
rows, cols = len(grid), len(grid[0])

def land_neighbours(r, c):
    count = 0
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
            count += 1
    return count

print(land_neighbours(1, 1), land_neighbours(0, 1))

2عدّ الجزر بالبحث بالعمق

كل خانة يابسة لم تُزر تبدأ جزيرة جديدة. نلوّن الجزيرة كلها بمكدّس حتى لا نعدّها مرة أخرى، ونحسب مساحتها أثناء ذلك:

grid = [[1, 1, 0, 0],
        [1, 0, 0, 1],
        [0, 0, 1, 1],
        [0, 0, 0, 1]]
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
rows, cols = len(grid), len(grid[0])
seen = set()

def explore(r, c):
    stack, area = [(r, c)], 0
    seen.add((r, c))
    while stack:
        r, c = stack.pop()
        area += 1
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
                seen.add((nr, nc))
                stack.append((nr, nc))
    return area

areas = [explore(r, c) for r in range(rows) for c in range(cols)
         if grid[r][c] == 1 and (r, c) not in seen]
print("islands:", len(areas), "areas:", areas)

3تمرين: المحيط

المحيط هو عدد حواف اليابسة التي تلمس ماء أو حافة الخريطة. لا تحتاج DFS هنا: مرّ على كل خانة يابسة، وأضف 4، واطرح 1 لكل جار يابسة (استخدم land_neighbours أعلاه). اختبر: خانة يابسة وحيدة محيطها 4، وخانتان متجاورتان محيطهما 6، وشبكة الصليب في المثال الأول محيطها 12.

مثال محلول

المسألة: صف واحد [[1,1,1]]. التحليل: 3 خانات × 4 = 12 حافة. الأزواج المتجاورة: (0,0)-(0,1) و(0,1)-(0,2)، كل زوج يخفي حافتين. الجواب: 12 − 4 = 8، وهو محيط مستطيل 3×1.

خرافة مقابل حقيقة

أين تقابله في العمل

اختبر فهمك

بطاقات مراجعة سريعة

تحقق من فهمك