สมมติว่าเรามีเมทริกซ์ขนาด m x n ที่ประกอบด้วย 0 และ 1 เราต้องหาว่ามี square submatrices (สี่เหลี่ยมจัตุรัส) กี่อันที่ประกอบด้วย 1 ทั้งหมด
เช่น ถ้าข้อมูลเข้าเป็น
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
ผลลัพธ์จะเป็น 15 เพราะมีสี่เหลี่ยมจัตุรัสขนาด 1 จำนวน 10 อัน ขนาด 2 จำนวน 4 อัน และขนาด 3 จำนวน 1 อัน รวม 10 + 4 + 1 = 15
ขั้นตอนการแก้ปัญหา
- ถ้าเมทริกซ์เป็น [[1]] ให้คืน 1
- rows = จำนวนแถว, cols = จำนวนคอลัมน์
- result = 0
- วนลูปทุก cell (row, col):
- ถ้าอยู่ที่แถวแรกหรือคอลัมน์แรก และค่าเป็น 1: result += 1
- มิฉะนั้น ถ้าค่าเป็น 1:
- square = 1 + min(matrix[row-1][col], matrix[row][col-1], matrix[row-1][col-1])
- อัปเดต matrix[row][col] = square (เก็บขนาดสี่เหลี่ยมสูงสุดที่มุมล่างขวาอยู่ที่นี่)
- result += square
- คืนค่า result
ตัวอย่างโค้ด
def solve(matrix):
if matrix == [[1]]:
return 1
rows = len(matrix)
cols = len(matrix[0])
result = 0
for row in range(rows):
for 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], matrix[row][col-1], matrix[row-1][col-1]) + 1
matrix[row][col] = square
result += square
return result
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(solve(matrix))
ข้อมูลเข้า
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
ข้อมูลออก
15
