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

มีเมทริกซ์ไบนารี 2D หาจำนวนสับเมทริกซ์สี่เหลี่ยมจัตุรัสที่ทุกค่าเป็น 1

เช่น เมทริกซ์ 5x4 ให้ 17 (12 ตัว 1x1, 4 ตัว 2x2, 1 ตัว 3x3)

ขั้นตอนการแก้ปัญหา

• DP: matrix[i][j] เก็บขนาดสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดลงท้ายที่ (i,j)
• ถ้า i==0 หรือ j==0: res += matrix[i][j]
• ถ้า matrix[i][j]==1: matrix[i][j] = min(ซ้าย, บน, ทับมุม) + 1; res += matrix[i][j]
• คืนค่า res

ตัวอย่างโค้ด

class Solution:
    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], matrix[i-1][j], matrix[i-1][j-1]) + 1
                    res += matrix[i][j]
        return res

ob = Solution()
matrix = [[1,1,1,0],[1,1,1,0],[1,1,1,0],[0,0,0,0],[1,0,1,1]]
print(ob.solve(matrix))

อินพุต

matrix = [[1,1,1,0],[1,1,1,0],[1,1,1,0],[0,0,0,0],[1,0,1,1]]

เอาต์พุต

17