โปรแกรมหาจำนวนสแควร์ซับเมทริกซ์ที่มี 1 ใน python

สมมติว่าเรามีเมทริกซ์ไบนารี 2 มิติ เราต้องหาจำนวนรวมของเมทริกซ์ย่อยที่มีทั้งหมด 1 วินาที

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

จากนั้นผลลัพธ์จะเป็น 17 เนื่องจากมี 12 (1 x 1) สี่เหลี่ยมจัตุรัส 4 (2 x 2) สี่เหลี่ยมและ 1 (3 x 3) สี่เหลี่ยมจัตุรัส

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

• res :=0
• สำหรับ i ในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
  • สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
    • ถ้าฉันเหมือนกับ 0 หรือ j เหมือนกับ 0 แล้ว
      • res :=res + matrix[i, j]
    • มิฉะนั้นเมื่อเมทริกซ์[i, j] เหมือนกับ 1 แล้ว
      • เมทริกซ์[i, j] =ค่าต่ำสุดของ (เมทริกซ์[i, j - 1], เมทริกซ์[i - 1, j] และเมทริกซ์[i - 1, j - 1]) + 1
      • res :=res + matrix[i, j]
• ผลตอบแทน

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

ตัวอย่าง

คลาสโซลูชัน:def Solve(self, matrix):res =0 for i in range(len(matrix)):for j in range(len(matrix[0])):if i ==0 or j ==0:res +=matrix[i][j] elif matrix[i][j] ==1:matrix[i][j] =min(matrix[i][j - 1] เมทริกซ์[i - 1 ][j], matrix[i - 1][j - 1]) + 1 res +=matrix[i][j] return resob =Solution()เมทริกซ์ =[ [1, 1, 1, 0], [1 , 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0], [1, 0, 1, 1]]print(ob.solve(matrix))

อินพุต

ผลลัพธ์

17