โปรแกรมนับจำนวนเกาะในเมทริกซ์ที่กำหนดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องหาจำนวนเกาะในเมทริกซ์ ในที่นี้ 1 คือดิน และ 0 สำหรับน้ำ ดังนั้นเกาะคือกลุ่ม 1s ที่อยู่ใกล้เคียงและมีน้ำล้อมรอบ เรากำลังพิจารณาว่าเพื่อนบ้านสามารถเป็นแนวนอนหรือแนวตั้งเท่านั้น ไม่ใช่แนวทแยง

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

แล้วผลลัพธ์จะเป็น 4

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

• กำหนดฟังก์ชัน explore() นี่จะเป็นแถว, โคล, เมทริกซ์
• ถ้า row และ col ไม่อยู่ในช่วงของ matrix หรือ matrix[row, col] จะเป็น 0 ดังนั้น
  • คืนสินค้า
• เมทริกซ์[แถว, คอลัมน์] :=0
• สำรวจ(แถว + 1, คอลัมน์, เมทริกซ์)
• สำรวจ(แถว - 1, col, เมทริกซ์)
• สำรวจ(แถว, col + 1, เมทริกซ์)
• สำรวจ(แถว, คอลัมน์ - 1, เมทริกซ์)
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• ถ้าเมทริกซ์เป็นโมฆะ
  • คืน 0
• หมู่เกาะ :=0
• สำหรับแถวที่อยู่ในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ให้ทำ
  • สำหรับ col ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
    • ถ้า matrix[row, col] เหมือนกับ 1 แล้ว
      • เกาะ :=เกาะ + 1
      • สำรวจ (แถว, คอลัมน์, เมทริกซ์)
• คืนเกาะ

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

ตัวอย่าง

คลาสโซลูชัน:def explore(self, row, col, matrix):if ( row <0 หรือ col <0 or row> len(matrix) - 1 or col> len (matrix[0]) - 1 หรือ matrix [แถว][col] ==0):return matrix[row][col] =0 self.explore(row + 1, col, matrix) self.explore(row - 1, col, matrix) self.explore(row) , col + 1, matrix) self.explore (แถว, col - 1, matrix) def แก้ (ตัวเอง, เมทริกซ์):ถ้าไม่ใช่เมทริกซ์:คืนค่า 0 เกาะ =0 สำหรับแถวในช่วง (len (เมทริกซ์)):สำหรับ col ใน range(len(matrix[0])):if matrix[row][col] ==1:islands +=1 self.explore(row, col, matrix) return islandsob =โซลูชัน() matrix =[ [1, 0 , 1, 0, 0], [0, 0, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 1, 0 , 1, 1], [1, 1, 1, 0, 1]]print(ob.solve(matrix))

อินพุต

ผลลัพธ์

4