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



Copyright (c) 2019-2024, Algotree.org.
All rights reserved.