คำอธิบายปัญหา
กำหนดเมทริกซ์ไบนารี 2D หาจำนวน **square submatrices** ทั้งหมดที่ element ทุกตัวเป็น 1
ตัวอย่าง
Matrix: 0 1 1 0 1 1
Output: 5 (1 ชุด 2x2 + 4 ชุด 1x1)
ขั้นตอนการแก้ปัญหา (DP)
dp[i][j]= ขนาด square ใหญ่สุดที่มุมล่างขวาอยู่ (i,j) และเป็น 1 ทั้งหมด- ถ้า
mat[i][j] == 1:- ขอบบน/ซ้าย:
dp = 1 - อื่นๆ:
dp = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
- ขอบบน/ซ้าย:
- ผลรวม
dp[i][j]ทุกช่อง = จำนวน square submatrices ทั้งหมด
การตนการทำงาน (Python)
def solve(mat):
if not mat:
return 0
c = 0
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j] == 1:
if i == 0 or j == 0:
c += 1
else:
temp = min(mat[i-1][j-1], mat[i][j-1], mat[i-1][j]) + mat[i][j]
c += temp
mat[i][j] = temp
return c
matrix = [[0, 1, 1], [0, 1, 1]]
print(solve(matrix)) # Output: 5
อินพุต / เอาต์พุต
Input: [[0, 1, 1], [0, 1, 1]] Output: 5
