C++ Online Compiler
Example: Maximum Size Square Submatrix in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Maximum Size Square Submatrix #include <iostream> #include <vector> #include <algorithm> // For std::min and std::max using namespace std; int maximalSquare(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty()) { return 0; } int rows = matrix.size(); int cols = matrix[0].size(); // dp[i][j] stores the side length of the largest square submatrix // with all 1s ending at (i-1, j-1) in the original matrix. // We use (rows + 1) and (cols + 1) for easier boundary handling. vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0)); int max_side = 0; // Iterate through the original matrix for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (matrix[i][j] == 1) { // If the current cell is '1', the size of the square ending here // depends on its top, left, and top-left neighbors in the DP table. dp[i + 1][j + 1] = 1 + min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}); // Update the maximum side found so far max_side = max(max_side, dp[i + 1][j + 1]); } // If matrix[i][j] is '0', then dp[i+1][j+1] remains 0 (default initialized) // as no square with all 1s can end at this position. } } return max_side * max_side; // Return the area } int main() { // Example 1: Matrix from the problem statement vector<vector<int>> matrix1 = { {1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0} }; cout << "Matrix 1: Max square area = " << maximalSquare(matrix1) << endl; // Expected: 9 // Example 2: All 1s matrix vector<vector<int>> matrix2 = { {1, 1, 1}, {1, 1, 1}, {1, 1, 1} }; cout << "Matrix 2: Max square area = " << maximalSquare(matrix2) << endl; // Expected: 9 // Example 3: Single 1 vector<vector<int>> matrix3 = {{1}}; cout << "Matrix 3: Max square area = " << maximalSquare(matrix3) << endl; // Expected: 1 // Example 4: No 1s vector<vector<int>> matrix4 = { {0, 0, 0}, {0, 0, 0} }; cout << "Matrix 4: Max square area = " << maximalSquare(matrix4) << endl; // Expected: 0 return 0; }
Output
Clear
ADVERTISEMENTS