全部为1的最大尺寸正方形子矩阵

给定二进制矩阵时,我们的任务是找到一个所有元素均为1的方阵。

对于这个问题,我们将创建一个辅助大小矩阵,其顺序与给定矩阵相同。该大小矩阵将有助于在每个条目中将Size [i,j]表示为全为1的方阵的大小。从该大小矩阵中,我们将获得最大数量,从而获得最大方阵的大小。

输入输出

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.

算法

subMatWithOne(given matrix)

输入-主矩阵。

输出-显示全部为1的方阵,其中最大的一个。

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

示例

#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();

}

输出结果

Subsquare matrix:

1 1 1

1 1 1

1 1 1

以上是 全部为1的最大尺寸正方形子矩阵 的全部内容, 来源链接: utcz.com/z/327154.html

回到顶部