# 全為 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 ```