โปรแกรมหาพื้นที่ของสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดของ 1 ในเมทริกซ์ที่กำหนดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องการหาสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดที่ประกอบด้วย 1 ในเมทริกซ์ที่กำหนดนั้น

เช่น ถ้าอินพุตเป็นดังนี้

ผลลัพธ์จะเป็น 16

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

• กำหนด res := 0
• วนลูป i จาก 0 ถึงขนาดของเมทริกซ์:
  • res := max(res, matrix[i][0])
• วนลูป i จาก 0 ถึงขนาดของเมทริกซ์[0]:
  • res := max(res, matrix[0][i])
• วนลูป i จาก 1 ถึงจำนวนแถวของเมทริกซ์:
  • วนลูป j จาก 1 ถึงจำนวนคอลัมน์ของเมทริกซ์:
    • ถ้า matrix[i][j] == 1 แล้ว:
      • matrix[i][j] = min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]) + 1
    • res = max(res, matrix[i][j])
• คืนค่า res^2

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

class Solution:
    def solve(self, matrix):
        res = 0
        for i in range(len(matrix)):
            res = max(res, matrix[i][0])
        for i in range(len(matrix[0])):
            res = max(res, matrix[0][i])
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]) + 1
                res = max(res, matrix[i][j])
        return res * res

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

อินพุต

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

เอาต์พุต

16