# Maximal Square

Question:
http://www.lintcode.com/en/problem/maximal-square/
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.

``````#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;
}
``````