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

สมมติว่าเรามีเมทริกซ์ไบนารีสองตัวคือ mat1 และ mat2 ในที่นี้ 1 หมายถึงดิน และ 0 หมายถึงน้ำ หากมีกลุ่มของ 1(แผ่นดิน) ล้อมรอบด้วยน้ำเรียกว่าเกาะ เราต้องหาจำนวนเกาะที่มีอยู่ทั้งใน mat1 และ mat2 ที่พิกัดเดียวกัน

ดังนั้นหากอินพุตเป็นเหมือน mat1 =

และ mat2 =

แล้วผลลัพธ์จะเป็น 2 เพราะเกาะที่ทับซ้อนกันคือ

จึงมีเกาะสองเกาะทับซ้อนกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• r :=จำนวนแถวของ mat1
• c :=จำนวนคอลัมน์ของ mat1
• last_row :=r - 1
• last_col :=c - 1
• กำหนดฟังก์ชัน mark() นี่จะใช้เวลา i, j
• mat1[i, j] :=0
• mat2[i, j] :=0
• ถ้าฉันไม่ใช่ศูนย์และ (mat1[i - 1, j] หรือ mat2[i - 1, j] อันใดอันหนึ่งไม่ใช่ศูนย์) ดังนั้น
  • เครื่องหมาย(i - 1, j)
• ถ้า j ไม่ใช่ศูนย์และ (mat1[i, j - 1] หรือ mat2[i, j - 1] อันใดไม่ใช่ศูนย์) ดังนั้น
  • เครื่องหมาย(i, j - 1)
• ถ้า j
• เครื่องหมาย(i, j + 1)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

[
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
[
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]

ผลลัพธ์

2