Python - หาสี่เหลี่ยมผืนผ้าที่เต็มไปด้วย 0 ใน Binary Matrix

ได้ binary 2D matrix ต้องการหาจุดเริ่มต้นและจุดสิ้นสุดของสี่เหลี่ยมผืนผ้าทั้งหมดที่เต็มไปด้วย 0 สี่เหลี่ยมแยกจากกัน (ไม่ติดกัน) แต่อาจติดขอบอาร์เรย์ สี่เหลี่ยมขนาด 1x1 ก็ได้

ตัวอย่าง

Input:

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

Output: [[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

Format: [start_row, start_col, end_row, end_col]

Python Implementation

def find_zero_rectangles(matrix):
    """หาสี่เหลี่ยมผืนผ้าที่เต็มไปด้วย 0 ทั้งหมด"""
    if not matrix or not matrix[0]:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    visited = [[False] * cols for _ in range(rows)]
    rectangles = []
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0 and not visited[i][j]:
                # หาขอบเขตของสี่เหลี่ยม
                r1, c1 = i, j
                
                # ขยายลง (rows)
                r2 = r1
                while r2 + 1 < rows and matrix[r2 + 1][j] == 0:
                    r2 += 1
                
                # ขยายขวา (cols) - ตรวจสอบทุกแถวใน range
                c2 = c1
                while c2 + 1 < cols:
                    # Check if all rows from r1 to r2 have 0 at column c2+1
                    if all(matrix[r][c2 + 1] == 0 for r in range(r1, r2 + 1)):
                        c2 += 1
                    else:
                        break
                
                # Mark visited
                for r in range(r1, r2 + 1):
                    for c in range(c1, c2 + 1):
                        visited[r][c] = True
                
                rectangles.append([r1, c1, r2, c2])
    
    return rectangles

# ทดสอบ
matrix = [
    [1, 0, 1, 1, 1, 0, 1],
    [1, 1, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 0, 1, 1],
    [1, 0, 1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1]
]

result = find_zero_rectangles(matrix)
print(result)
# [[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], 
#  [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

อัลกอริธึมต้นฉบับ (Mark as 5)

โค้ดต้นฉบับใช้การ mark ค่า 5 แทน visited array:

def find_rect_original(i, j, a, output, index):
    x, y = len(a), len(a[0])
    flag_col = flag_row = 0
    
    for m in range(i, x):
        if a[m][j] == 1:
            flag_row = 1
            break
        if a[m][j] == 5:
            continue
        
        for n in range(j, y):
            if a[m][n] == 1:
                flag_col = 1
                break
            a[m][n] = 5  # Mark visited
        
        if flag_row:
            output[index].append(m - 1)
        else:
            output[index].append(m)
        
        if flag_col:
            output[index].append(n - 1)
        else:
            output[index].append(n)

def get_coord_original(a):
    n = len(a)
    op = []
    idx = -1
    for i in range(n):
        for j in range(len(a[0])):
            if a[i][j] == 0:
                op.append([i, j])
                idx += 1
                find_rect_original(i, j, a, op, idx)
    return op

การปรับปรุง (Improvements)

Complexity

• Time: O(rows × cols) - แต่ละเซลล์เยี่ยมชมได้สูงสุด 1 ครั้ง
• Space: O(rows × cols) - visited array

สมมติฐานสำคัญ

• สี่เหลี่ยมไม่ overlap/ติดกัน (separated by 1s)
• รูปร่างเป็นสี่เหลี่ยมผืนผ้าแท้ (solid rectangle of 0s)
• Single cell = valid rectangle