Maximum Size Square Submatrix ทั้งหมดเป็น 1

กำหนด Binary Matrix (มีแค่ 0 และ 1) ต้องการหา Square Submatrix ขนาดใหญ่ที่สุด ที่ทุกค่าเป็น 1

ตัวอย่าง Input และ Output

Input Matrix (6x5):
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output: Subsquare matrix (ขนาด 3x3):
1 1 1
1 1 1
1 1 1

อัลกอริทึม Dynamic Programming

ฟังก์ชัน subMatWithOne(matrix)

แนวคิด: Auxiliary Matrix

สร้าง subMat[i][j] = ขนาดของ square submatrix ที่มุมขวาล่างอยู่ที่ (i,j) และประกอบด้วย 1 ทั้งหมด

Recurrence Relation:

• ถ้า matrix[i][j] == 0 → subMat[i][j] = 0
• ถ้า matrix[i][j] == 1 → subMat[i][j] = 1 + min(subMat[i-1][j], subMat[i][j-1], subMat[i-1][j-1])

เหตุผล: Square ขนาด k ที่มุม (i,j) ต้องการ square ขนาด k-1 ที่ (i-1,j), (i,j-1), (i-1,j-1) เป็น 1 ทั้งหมด

ขั้นตอน:

1. คัดลอกแถวแรกและคอลัมน์แรกจาก matrix → subMat
2. for i = 1..ROW-1, j = 1..COL-1: ใช้ recurrence ข้างต้น
3. หา maxSize และตำแหน่ง (iMax, jMax) ใน subMat
4. พิมพ์ submatrix จาก (iMax, jMax) ย้อนกลับขนาด maxSize

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

#include <iostream>
#include <algorithm>
#define ROW 6
#define COL 5
using namespace std;

int matrix[ROW][COL] = {
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}
};

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

void subMatWithOne() {
    int subMat[ROW][COL];
    int maxSize, iMax, jMax;

    // คัดลอกแถวแรกและคอลัมน์แรก
    for(int i = 0; i < ROW; i++) subMat[i][0] = matrix[i][0];
    for(int j = 0; j < COL; j++) subMat[0][j] = matrix[0][j];

    // DP
    for(int i = 1; i < ROW; i++) {
        for(int j = 1; j < COL; j++) {
            if(matrix[i][j] == 1)
                subMat[i][j] = min3(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
            else
                subMat[i][j] = 0;
        }
    }

    // หาค่าสูงสุด
    maxSize = subMat[0][0]; iMax = 0; jMax = 0;
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            if(maxSize < subMat[i][j]) {
                maxSize = subMat[i][j];
                iMax = i; jMax = j;
            }

    // พิมพ์ผลลัพธ์
    cout << "Subsquare matrix:" << endl;
    for(int i = iMax; i > iMax - maxSize; i--) {
        for(int j = jMax; j > jMax - maxSize; j--)
            cout << matrix[i][j] << " ";
        cout << endl;
    }
}

int main() { subMatWithOne(); return 0; }

Output

Subsquare matrix:
1 1 1
1 1 1
1 1 1

ความซับซ้อน

• Time: O(ROW × COL)
• Space: O(ROW × COL) (ลดเป็น O(COL) ได้)

การขยาย: Rectangle Submatrix ทั้ง 1 (ไม่จำเป็นต้องเป็นสี่เหลี่ยมจัตุรัส)

ใช้ Histogram + Largest Rectangle in Histogram (O(ROW × COL))