โปรแกรมนับจำนวนเกาะที่ทับซ้อนกันในสองแผนที่ด้วย Python

ตัวอย่าง

หากอินพุตเป็นดังนี้:

mat1 = [[1, 0, 1],
        [1, 0, 0],
        [1, 0, 0]]

mat2 = [[1, 0, 1],
        [1, 0, 0],
        [1, 0, 1]]

เอาต์พุทจะเป็น 2 เนื่องจากมีเกาะที่ทับซ้อนกันสองแห่ง (คอลัมน์แรกและแถวแรก-คอลัมน์ที่สาม)

ขั้นตอนการแก้ปัญหา

1. กำหนด r = จำนวนแถวของ mat1, c = จำนวนคอลัมน์
2. สร้างฟังก์ชัน mark(i, j) เพื่อทำเครื่องหมายเซลล์ที่เยี่ยมชมแล้ว:
   • ตั้งค่า mat1[i][j] = mat2[i][j] = 0
   • ตรวจสอบเพื่อนบน 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) หากเป็นที่ดินในเมทริกซ์ใดเมทริกซ์หนึ่ง ให้เรียก mark แบบรีเคอร์ซีฟ
3. ลูปผ่านทุกเซลล์: หาก mat1[i][j] != mat2[i][j] ให้เรียก mark(i, j) เพื่อกำจัดเกาะที่ไม่ตรงกัน
4. นับเกาะที่เหลือใน mat1 (ซึ่งจะตรงกับ mat2 แล้ว) โดยใช้ mark อีกครั้ง

การตนการทำงาน (Python)

def solve(mat1, mat2):
    r = len(mat1)
    c = len(mat1[0])
    last_row = r - 1
    last_col = c - 1
    
    def mark(i, j):
        mat1[i][j] = mat2[i][j] = 0
        if i and (mat1[i - 1][j] or mat2[i - 1][j]):
            mark(i - 1, j)
        if j and (mat1[i][j - 1] or mat2[i][j - 1]):
            mark(i, j - 1)
        if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
            mark(i, j + 1)
        if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
            mark(i + 1, j)
    
    # กำจัดเกาะที่ไม่ตรงกัน
    for i in range(r):
        for j in range(c):
            if mat1[i][j] != mat2[i][j]:
                mark(i, j)
    
    islands = 0
    # นับเกาะที่เหลือ (ซึ่งตรงกันแล้ว)
    for i in range(r):
        for j in range(c):
            if mat1[i][j]:
                islands += 1
                mark(i, j)
    return islands

mat1 = [[1, 0, 1], [1, 0, 0], [1, 0, 1]]
mat2 = [[1, 0, 1], [1, 0, 0], [1, 0, 0]]
print(solve(mat1, mat2))  # Output: 2

อินพุต / เอาต์พุต

Input:  [[1, 0, 1], [1, 0, 0], [1, 0, 1]], [[1, 0, 1], [1, 0, 0], [1, 0, 0]]
Output: 2