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