โปรแกรมค้นหาจำนวนรูปร่างเกาะที่แตกต่างจากเมทริกซ์ที่กำหนดใน Python

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

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

แล้วเอาท์พุตจะเป็น 4 (เกาะแยกเป็นสีต่างกัน)

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

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา i, j, k, l

• mat[i, j] :=0

• ใส่คู่ (i − k, j − l) ที่ส่วนท้ายของรูปร่าง

• ถ้า i + 1 <จำนวนแถวของ mat และ mat[i + 1, j] คือ 1 แล้ว

  • dfs(i + 1, j, k, l)

• ถ้า j + 1 <จำนวนคอลัมน์ของ mat และ mat[i, j + 1] เป็น 1 แล้ว

  • dfs(i, j + 1, k, l)

• ถ้า i − 1>=0 และ mat[i − 1, j] คือ 1 แล้ว

  • dfs(i − 1, j, k, l)

• ถ้า j − 1>=0 และ mat[i, j − 1] เป็น 1 แล้ว

  • dfs(i, j − 1, k, l)

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• cnt :=0

• รูปร่าง :=ชุดใหม่

• สำหรับฉันอยู่ในช่วง 0 ถึงแถวนับเสื่อทำ

  • สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของ mat ให้ทำ

    • ถ้า mat[i, j] คือ 1 แล้ว

      • รูปร่าง :=รายการใหม่

      • dfs(i, j, i, j)

      • ถ้ารูปร่างไม่อยู่ในรูปร่างแล้ว

        • cnt :=cnt + 1

      • แทรกรูปร่างลงในรูปร่าง

• ส่งคืน cnt

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

ตัวอย่าง

คลาสโซลูชัน:def แก้(ตัวเอง, mat):def dfs(i, j, k, l):mat[i][j] =0 shape.append((i − k, j − l)) ถ้า i + 1 =0 and mat[i − 1][j]:dfs(i − 1, j, k, l) if j − 1>=0 และ mat[i][j − 1]:dfs(i, j − 1, k, l) cnt =0 รูปร่าง =set() สำหรับฉัน ในช่วง (len(mat)):สำหรับ j ในช่วง ( len(mat[0])):if mat[i][j]:shape =[] dfs(i, j, i, j) shape =tuple(shape) ถ้ารูปร่างไม่อยู่ในรูปร่าง:cnt +=1 รูปร่าง เพิ่ม (รูปร่าง) ส่งคืน cntob =โซลูชัน () เมทริกซ์ =[ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [ 0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1]]print(ob.solve(matrix))

อินพุต

ผลลัพธ์

4