// A Lab Test 2 Answer
// CS 176, Summer 2001


#include <cassert>


static int fls(const int mtx[25][25], int x, int y, int m, int n);


struct square {
  int upper_left_x, upper_left_y, size;
  };


// First, implement the original algorithm to find a largest square.

square find_largest_square(const int mtx[25][25], int m, int n) {

  // Given the m-by-n matrix mtx, find and regurn a square of uniform value in
  // mtx that is at least as large as any other square of uniform value in mtx.

  square s;

  s.upper_left_x = 0;
  s.upper_left_y = 0;
  s.size = 0;

  // Sanity checks.  Return the empty square if they fail.

     if ((m < 0) || (m > 25)) return s;
     if ((n < 0) || (n > 25)) return s;
  
  // Go through mtx finding the largest square at each element and remembering
  // the largest square found overall.

     for (int x = 0; x < m; x++)
       for (int y = 0; y < n; y++) {
	 const int size = fls(mtx, x, y, m, n);
	 if (size > s.size) {
	   s.upper_left_x = x;
	   s.upper_left_y = y;
	   s.size = size;
	   }
	 }

  // That's it; return the largest square founnd.

     return s;
  }


static int fls(const int mtx[25][25], int x, int y, int m, int n) {

  // Given the n-by-m matrix mtx, return the size of the largest square having
  // its upper-left element at mtx[x][y].

  // Sanity checks; die if any of them fail.

     assert((0 <= m) && (m <= 25));
     assert((0 <= n) && (n <= 25));
     assert((0 <= x) && (x < m));
     assert((0 <= y) && (y < n));

  int s = 1;

  while ((x + s < m) && (y + s < n)) {
    for (int i = 0; i < s; i++) {
      if (mtx[x + s - 1][y + i] != mtx[x + s][y + i])
	return s;
      if (mtx[x + i][y + s - 1] != mtx[x + i][y + s])
	return s;
      }
    if (mtx[x + s - 1][y + s - 1] != mtx[x + s][y + s])
      return s;
    s++;
    }

  return s;
  }


// Now for the optimizations.  The first optimization avoids finding the
// largest square at mtx[x][y] when mtx[x][y] is too close to the edge of the
// matrix.  Here "too close" means either (n - s <= x < n) or (m - s <= y < m)
// where s is the size of the largest square found so far.  In either case, the
// square at mtx[x][y] can't be larger than s, so there's no reason to to
// consider the square further. (This description assumes the elements of mtx
// are scanned left-to-right and top-to-bottom; other scan orders would require
// different bounds on x and y, but the principle is the same in all cases.)
//
// The changes required to find_largest_square() to implement this optimization
// are pretty simple: make sure x and y don't get too close to the edge of mtx.
// This means just changing the upper bounds of the two for loops.  Note that
// the bounds passed in the call to fls() don't change; it would be incorrect
// to have
//
//   const int size = fls(mtx, x, y, m - s.size, n - s.size);
//
// The bounds on x and y are for the upper-left element of the square; fls()
// needs to consider the whole square and so needs to get as close to the
// matrix edge as it needs.


square find_largest_square_one(const int mtx[25][25], int m, int n) {

  // Given the m-by-n matrix mtx, find and regurn a square of uniform value in
  // mtx that is at least as large as any other square of uniform value in mtx.

  square s;

  s.upper_left_x = 0;
  s.upper_left_y = 0;
  s.size = 0;

  // Sanity checks.  Return the empty square if they fail.

     if ((m < 0) || (m > 25)) return s;
     if ((n < 0) || (n > 25)) return s;
  
  // Go through mtx finding the largest square at each element and remembering
  // the largest square found overall.

     for (int x = 0; x < n - s.size; x++)
       for (int y = 0; y < m - s.size; y++) {
	 const int size = fls(mtx, x, y, m, n);
	 if (size > s.size) {
	   s.upper_left_x = x;
	   s.upper_left_y = y;
	   s.size = size;
	   }
	 }

  // That's it; return the largest square founnd.

     return s;
  }


// fls() needs no changes for the first optimization.

// The second optimization involves the way fls() finds the largest square.
// Rather than start size at 1, start it from one less than the size of the
// square at the element up and to the left of the current element.  Because
// the starting size gets passed in as a prameter, the changes needed to lfs()
// are simple: add a parameter and delete the local declaration of s.


static int fls_two(const int mtx[25][25], int s, int x, int y, int m, int n) {

  // Given the n-by-m matrix mtx, return the size of the largest square having
  // its upper-left element at mtx[x][y].  Start counting square size from s.

  // Sanity checks; die if any of them fail.

     assert((0 <= m) && (m <= 25));
     assert((0 <= n) && (n <= 25));
     assert((0 <= x) && (x < n));
     assert((0 <= y) && (y < m));
     assert(1 <= s);

  while ((x + s < n) && (y + s < m)) {
    for (int i = 0; i < s; i++) {
      if (mtx[x + s - 1][y + i] != mtx[x + s][y + i])
	return s;
      if (mtx[x + i][y + s - 1] != mtx[x + i][y + s])
	return s;
      }
    if (mtx[x + s - 1][y + s - 1] != mtx[x + s][y + s])
      return s;
    s++;
    }

  return s;
  }


// The changes needed in find_largest_square() are a bit more complicated
// because it needs to remember the size of the largest squares at each
// element.  The easiest way to remember the sizes is to store them in a matrix
// so that the sizes[x][y] holds size of the largest square at mtx[x][y].
//
// Some care is necessary when using this scheme because the initial size to
// use when computing the size of the largest square at mtx[x][y] is sizes[x -
// 1][y - 1] (that is, one less than the size of the square up and to the left
// of this square).  The means the initial size for the square at mtx[0][0] is
// sizes[-1][-1], which doesn't exist.
//
// Fortunately, this problem is easy to deal with by shifting sizes down and to
// the right one element; that is sizes[x + 1][y + 1] holds the size of the
// largest square at mtx[x][y].  Notice this shift moves the problem to the
// other end of the matrix; now size[m][n] holds the size of the square at
// mtx[m - 1][n - 1].  However, this problem is easy to solve: make sure the
// size matrix is (m + 1)-by-(n + 1).
//
// There is one more problem to deal with before we can write the code.  What
// is the initial size of the square at mtx[0][0]?  The problem is, there's no
// square up and to the right of mtx[0][0] (every element along the top and
// left-edge of mtx has this problem).  Fortunately, this problem is also easy
// to deal with: just pretend there are squares that have size 1.  Initializing
// sizes to have 1s along the top and left-edge elements does the trick.


square find_largest_square_two(const int mtx[25][25], int m, int n) {

  // Given the m-by-n matrix mtx, find and regurn a square of uniform value in
  // mtx that is at least as large as any other square of uniform value in mtx.

  square s;

  s.upper_left_x = 0;
  s.upper_left_y = 0;
  s.size = 0;

  // Sanity checks.  Return the empty square if they fail.

     if ((m < 0) || (m > 25)) return s;
     if ((n < 0) || (n > 25)) return s;
  
  // Go through mtx finding the largest square at each element and remembering
  // the largest square found overall.

     int square_sizes[25 + 1][25 + 1];

     for (int i = 0; i < 26; i++) {
       square_sizes[0][i] = 1;
       square_sizes[i][0] = 1;
       }

     for (int x = 0; x < m; x++)
       for (int y = 0; y < n; y++) {
	 square_sizes[x + 1][y + 1] = 
	   fls_two(mtx, square_sizes[x][y], x, y, m, n);
	 if (square_sizes[x + 1][y + 1] > s.size) {
	   s.upper_left_x = x;
	   s.upper_left_y = y;
	   s.size = square_sizes[x + 1][y + 1];
	   }
	 }

  // That's it; return the largest square founnd.

     return s;
  }