Maximal Square

Question:
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Example

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Answer:
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

int maxSquarea(vector<vector<int> >& matrix) {
  int m = matrix.size();
  int n = matrix[0].size();
  vector<vector<int> >  matrix_flag = matrix;
  int r = 0;
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      matrix_flag[i][j] = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 0)
        continue;
      if (matrix_flag[i][j] == 1)
        continue;
      int k = 1;
      while (1) {
        bool all1 = true;
        int ii = i + k;
        int jj;
        for (jj = 0; jj <= k && ii < m && j+jj < n; jj++) {
          if (matrix[ii][j+jj] == 0) {
            all1 = false;
            break;
          }
        }
        if (!all1 || ii >= m || ((jj <= k) && (j + jj >= n)))
          break;
        jj = j + k;
        for (ii = 0; ii <= k && i+ii < m && jj < n; ii++) {
          if (matrix[i+ii][jj] == 0) {
            all1 = false;
            break;
          }
        }
        if (!all1 || ((ii <= k) && (i + ii >= m)) || jj >= n)
          break;
        k++;
      }
      if (k > 1)
        cout << i << " " << j << " " << k << endl;
      for (int jj = j; jj < j + k; jj++)
          matrix_flag[i][jj] = 1;
      if (k > r)
        r = k;
    }
  }
  return r;
}

void printMatrix(vector<vector<int> >& matrix) {
  int m = matrix.size();
  int n = matrix[0].size();
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      cout << matrix[i][j] << " ";
    }
    cout << endl;
  }
}

void buildMatrix(vector<vector<int> >& matrix) {
  int m = 10;
  int n = 10;
  srand(time(0));
  for (int i = 0; i < m; i++) {
    vector<int> row;
    for (int j = 0; j < n; j++) {
      if (rand()%2)
        row.push_back(0);
      else
        row.push_back(1);
    }
    matrix.push_back(row);
  }
}

int main() {
  vector<vector<int> > matrix;
  buildMatrix(matrix);
  printMatrix(matrix);
  cout << maxSquarea(matrix) << endl;
  return 0;
}

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️