# 全为 1 的最大尺寸正方形子矩阵 > 原文： [https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/](https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/) 给定一个二进制矩阵，找出全为 1 的最大尺寸平方子矩阵。 例如，考虑下面的二进制矩阵。  算法： 令给定的二进制矩阵为 M [R] [C]。 该算法的思想是构造一个辅助大小矩阵 S [] []，其中每个条目 S [i] [j]表示正方形子矩阵的大小，所有 1 包括 M [i] [j]，其中 M [ i] [j]是子矩阵中最右边和最下面的条目。 ``` 1) Construct a sum matrix S[R][C] for the given M[R][C]. a) Copy first row and first columns as it is from M[][] to S[][] b) For other entries, use following expressions to construct S[][] If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 2) Find the maximum entry in S[R][C] 3) Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][] ``` 对于上述示例中给定的 M [R] [C]，构造的 S [R] [C]将为： ``` 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0 ``` 上述矩阵中最大条目的值为 3，条目的坐标为（4，3）。 使用最大值及其坐标，我们可以找到所需的子矩阵。 ## C++ ```cpp // C++ code for Maximum size square  // sub-matrix with all 1s  #include <bits/stdc++.h> #define bool int  #define R 6  #define C 5  using namespace std; void printMaxSubSquare(bool M[R][C])  {      int i,j;      int S[R][C];      int max_of_s, max_i, max_j;      /* Set first column of S[][]*/     for(i = 0; i < R; i++)          S[i][0] = M[i][0];      /* Set first row of S[][]*/     for(j = 0; j < C; j++)          S[0][j] = M[0][j];      /* Construct other entries of S[][]*/     for(i = 1; i < R; i++)      {          for(j = 1; j < C; j++)          {              if(M[i][j] == 1)                  S[i][j] = min(S[i][j-1],min( S[i-1][j],                                  S[i-1][j-1])) + 1;              else                 S[i][j] = 0;          }      }      /* Find the maximum entry, and indexes of maximum entry          in S[][] */     max_of_s = S[0][0]; max_i = 0; max_j = 0;      for(i = 0; i < R; i++)      {          for(j = 0; j < C; j++)          {              if(max_of_s < S[i][j])              {                  max_of_s = S[i][j];                  max_i = i;                  max_j = j;              }          }                  }      cout<<"Maximum size sub-matrix is: \n";      for(i = max_i; i > max_i - max_of_s; i--)      {          for(j = max_j; j > max_j - max_of_s; j--)          {              cout << M[i][j] << " ";          }          cout << "\n";      }  }  /* Driver code */ int main()  {      bool M[R][C] = {{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}};      printMaxSubSquare(M);  }  // This is code is contributed by rathbhupendra ```