The C++ Program: maximum-square.cpp
1 #include <iostream>
2 #include <cstdlib>
3 #include <cmath>
4 using namespace std;
5
6 int main()
7 {
8 int rows, cols;
9 cin >> rows >> cols;
10 while (rows > 0)
11 {
12
13 int grid[rows][cols];
14
15
16 int squareSize[rows][cols];
17
18
19 for (int i = 0; i < rows; i++)
20 for (int j = 0; j < cols; j++)
21 cin >> grid[i][j];
22
23 for (int r = rows-1; r >= 0; r--)
24 {
25 for (int c = cols-1; c >= 0; c--)
26 {
27
28 if (grid[r][c] == 1)
29 {
30
31
32 if (r == rows-1 || c == cols-1)
33 {
34 squareSize[r][c] = 1;
35 }
36
37
38
39 else
40 {
41 int bestSize = squareSize[r+1][c];
42 bestSize = min(bestSize, squareSize[r][c+1]);
43 bestSize = min(bestSize, squareSize[r+1][c+1]);
44 squareSize[r][c] = bestSize + 1;
45 }
46 }
47
48 else
49 {
50 squareSize[r][c] = 0;
51 }
52 }
53 }
54
55
56 int maxSize = 0;
57 for (int i = 0; i < rows; i++)
58 for (int j = 0; j < cols; j++)
59 maxSize = max(maxSize, squareSize[i][j]);
60
61 cout << maxSize << endl;
62
63 cin >> rows >> cols;
64 }
65 }