Kích thước tối đa submatrix hình vuông với tất cả 1s

Khi cho ma trận nhị phân, nhiệm vụ của chúng ta là tìm một ma trận vuông có tất cả các phần tử là 1.

Đối với bài toán này, chúng ta sẽ tạo một ma trận kích thước phụ, có thứ tự giống như ma trận đã cho. Ma trận kích thước này sẽ giúp biểu diễn, trong mỗi mục nhập Kích thước [i, j], là kích thước của ma trận vuông với tất cả các 1s. Từ ma trận kích thước đó, chúng ta sẽ nhận được số lớn nhất để có kích thước của ma trận vuông lớn nhất.

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

Input:
The binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 1
0 0 0 0 0

Output:
The largest submatrix with all 1’s.

Thuật toán

subMatWithOne(given matrix)

Đầu vào - Ma trận chính.

Đầu ra - Hiển thị ma trận vuông với tất cả 1, ma trận nào là lớn nhất.

Begin
   define subMat whose order is same as given matrix
   copy first row and first column of given matrix to subMat

   for all row i (1 to n), do
      for all column j (1 to n), do
         if matrix[i, j] = 1, then
            subMat[i, j] := 1 + minimum of subMat[i, j-1]
            and subMat[i-1, j-1]
         else
            subMat[i, j] := 0
      done
   done

   maxSize := subMat[0, 0], iMax := 0 and jMax := 0
   for all row i and column j, do
      if maxSize < subMat[i, j], then
         maxSize := subMat[i, j]
         iMax := i, jMax := j
   done

   print sub matrix from row = iMax to (iMax - maxSize), and column jMax to (jMax - maxSize)
End

Ví dụ

#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 ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

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

   for(int i = 0; i < ROW; i++)    //copy first row of matrix to sub matrix
      subMat[i][0] = matrix[i][0];

   for(int j = 0; j < COL; j++)    //copy first column of matrix to sub matrix
      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)    //find minimum of left, top and diagonal element + 1
            subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
         else
            subMat[i][j] = 0;    //if item is 0, put only 0
      }  
   }

   maxSize = subMat[0][0]; iMax = 0; jMax = 0;
   for(int i = 0; i < ROW; i++) {    //find the order of sub square matrix

      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--) {    //print the submatrix using max size
      for(int j = jMax; j > jMax - maxSize; j--) {
         cout << matrix[i][j]<<" ";
      }
      cout << endl;
   }
}  
 
int main() {
   subMatWithOne();
} 

Đầu ra

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