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           // The grid itself
 13           int grid[rows][cols];
 14     
 15           // Size of the maximum square with its upper left corner in this cell
 16           int squareSize[rows][cols]; 
 17           
 18           // Input the grid
 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                   // There can only be a square if the cell contains a 1
 28                   if (grid[r][c] == 1)
 29                   {
 30                      // There can't be any squares bigger than 1 with upper left
 31                      // corner in the last row or column.
 32                      if (r == rows-1 || c == cols-1)
 33                      {
 34                         squareSize[r][c] = 1;
 35                      }
 36                      // You can only have a square of size n with upper left
 37                      // corner at (r,c) if there are squares of size n-1 at
 38                      // (r+1, c), (r, c+1), and (r+1, c+1).
 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                   // if the square is 0, set the size to 0
 48                   else
 49                   {
 50                       squareSize[r][c] = 0;
 51                   }
 52               }
 53           }
 54           
 55           // Find the biggest square
 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 }