โปรแกรมนับจำนวนเมทริกซ์ย่อยแบบสี่เหลี่ยมกับทุกอันโดยใช้ Python

สมมติว่าเรามีเมทริกซ์ไบนารี m x n เราต้องค้นหาว่าเมทริกซ์ย่อยกำลังสองมีทั้งหมดกี่ตัว

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

ผลลัพธ์จะเป็น 15 เนื่องจากมี 10 สี่เหลี่ยมของด้าน 1 4 สี่เหลี่ยมของด้าน 2 และ 1 สแควร์ของด้าน 3 จากนั้นจำนวนทั้งหมดของสแควร์ส =10 + 4 + 1 =15

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

• ถ้าเมทริกซ์มีอันเดียว แล้ว

  • กลับ 1

• แถว :=จำนวนแถวของเมทริกซ์

• cols :=จำนวนคอลัมน์ของเมทริกซ์[0]

• ผลลัพธ์ :=0

• สำหรับแถวที่อยู่ในช่วง 0 ถึงแถว - 1 ทำ

  • สำหรับ col ในช่วง 0 ถึง cols - 1 ทำ

    • ถ้าแถวเหมือนกับ 0 หรือ col เหมือนกับ 0 แล้ว

      • ถ้า matrix[row, col] เหมือนกับ 1 แล้ว

        • ผลลัพธ์ :=ผลลัพธ์ + 1

      • มิฉะนั้นเมื่อ matrix[row, col] เหมือนกับ 1 แล้ว

        • square :=1 + (ค่าต่ำสุดของ matrix[row-1,col], matrix[row,col-1] และ matrix[row-1,col-1])

        • matrix[แถว, col] :=สี่เหลี่ยม

        • ผลลัพธ์ :=ผลลัพธ์ + สี่เหลี่ยม

• ส่งคืนผลลัพธ์

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

ตัวอย่าง

def Solve(matrix):if matrix ==[[1]]:return 1 rows =len(matrix) cols =len(matrix[0]) ผลลัพธ์ =0 สำหรับแถวในช่วง (แถว):สำหรับ col in range(cols):if (row ==0 or col ==0):if matrix[row][col] ==1:result +=1 elif matrix[row][col] ==1:square =min() matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1 matrix[row][col] =กำลังสองผลลัพธ์ +=กำลังสอง ผลตอบแทนเมทริกซ์ =[[0,1,1,1],[1,1,1,1],[0,1,1,1]]print(solve(matrix))

อินพุต

ผลลัพธ์

15