# Finding biggest 1 filled square in a binary matrix

C++ program for finding the biggest 1 filled square matrix

``````#include<iostream>
#include<vector>

using namespace std;

class Matrix {

public:
int MaximalSquare (vector<vector<char>>& matrix) {

int rows = matrix.size();
int cols = matrix[0].size();

// Assumption is that the size of the matrix doesn't exceed 300 x 300
int table[301][301] = {{ 0 }};

// Base case
// Fill the last column
for (int r = 0; r < rows; r++) {
if (matrix[r][cols-1] == '1')
table[r][cols-1] = 1;
}

// Fill the last row
for (int c = 0; c < cols; c++) {
if (matrix[rows-1][c] == '1')
table[rows-1][c] = 1;
}

for (int r = rows-2; r >= 0; r--) {
for (int c = cols-1; c >= 0; c--) {
if (matrix[r][c] != '0') {
table[r][c] = min (table[r][c+1], table[r+1][c]);
table[r][c] = 1 + min (table[r][c], table[r+1][c+1]);
}
}
}

int area = 0;
int max_area = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
area = max (area, table[r][c]);
if (area * area > max_area)
max_area = area * area;
}
}
return max_area;
}

void Display (vector<vector<char>> & matrix) {

int rows = matrix.size();
int cols = matrix[0].size();

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++)
cout << matrix[r][c] << " ";
cout << endl;
}
}
};

int main() {

Matrix M;
vector<vector<char>> matrix_1 = {{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}};

M.Display (matrix_1);
cout << "Maximal Square Size : " << M.MaximalSquare(matrix_1) << endl << endl;

vector<vector<char>> matrix_2 = {{'1','0'},
{'0','1'}};
M.Display (matrix_2);
cout << "Maximal Square Size : " << M.MaximalSquare(matrix_2);

return 0;
}
``````

Output

``````1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Maximal Square Size : 4

1 0
0 1
Maximal Square Size : 1
``````