โปรแกรมนับจำนวน submatrices ที่เป็น 1 ทั้งหมดด้วย Python

สมมติว่าเรามีเมทริกซ์ขนาด m x n ที่ประกอบด้วย 0 และ 1 เราต้องหาว่ามี submatrices กี่อันที่ประกอบด้วย 1 ทั้งหมด

เช่น ถ้าข้อมูลเข้าเป็น

ผลลัพธ์จะเป็น 13 เพราะมี 6 เมทริกซ์ 1x1, 3 เมทริกซ์ 2x1, 2 เมทริกซ์ 1x2, 1 เมทริกซ์ 3x1 และ 1 เมทริกซ์ 2x2 (หมายเหตุ: ตัวอย่างเดิมเขียน 4x4 ผิด ควรเป็น 2x2)

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

• m = จำนวนแถว, n = จำนวนคอลัมน์
• สร้าง dp ขนาด m x n เติม 0
• คำนวณความสูงของ 1 ติดต่อกันในแนวดิ่ง:
  • ถ้า i == 0 และ matrix[i][j] == 1: dp[i][j] = 1
  • ถ้า matrix[i][j] == 1: dp[i][j] = dp[i-1][j] + 1
• total = 0
• สำหรับแต่ละแถว i และคอลัมน์ j:
  • วน k จาก j+1 ถึง n:
    • total += min(dp[i][j:k]) (ความสูงต่ำสุดในช่วงคอลัมน์ j ถึง k-1)
• คืนค่า total

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

def solve(matrix):
    m = len(matrix)
    n = len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and matrix[i][j]:
                dp[i][j] = 1
            elif matrix[i][j]:
                dp[i][j] = dp[i-1][j] + 1
    total = 0
    for i in range(m):
        for j in range(n):
            for k in range(j+1, n+1):
                total += min(dp[i][j:k])
    return total

matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

ข้อมูลเข้า

[[1,0,1],[0,1,1],[0,1,1]]

ข้อมูลออก

13