Ma trận con vuông toàn 1 lớn nhất

Cho ma trận nhị phân (0/1), tìm ma trận con vuông (square submatrix) lớn nhất chỉ chứa toàn 1.

Xây dựng ma trận phụ subMat cùng kích thước, trong đó subMat[i][j] = kích thước ma trận vuông toàn 1 lớn nhất **kết thúc** tại (i,j) (là góc dưới phải).

Đầu vào và Đầu ra

Đầu vào: Ma trận 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

Đầu ra: Ma trận con vuông 3x3 toàn 1 (kích thước 3)

Thuật toán

1. Sao chép hàng 0 và cột 0 từ ma trận gốc sang subMat.
2. Với i,j ≥ 1:
   • Nếu matrix[i][j] == 1: subMat[i][j] = 1 + min(subMat[i-1][j], subMat[i][j-1], subMat[i-1][j-1]).
   • Ngược lại: subMat[i][j] = 0.
3. Tìm giá trị lớn nhất trong subMat → đó là kích thước ma trận vuông lớn nhất. Vị trí của nó cho góc dưới phải.

Ví dụ C++

#include <iostream>
#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 min(int a,int b,int c) { return min(min(a,b),c); }

void subMatWithOne() {
    int subMat[ROW][COL];
    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];

    for(int i=1;i<ROW;i++)
        for(int j=1;j<COL;j++)
            if(matrix[i][j]==1)
                subMat[i][j] = min(subMat[i][j-1],subMat[i-1][j],subMat[i-1][j-1])+1;
            else subMat[i][j]=0;

    int 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:\n";
    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(); }

Kết quả

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