C++ में अधिकतम वर्ग

मान लीजिए हमारे पास 0 और 1 से भरा एक 2D बाइनरी मैट्रिक्स है। हमें केवल 1 वाले सबसे बड़े वर्ग का क्षेत्रफल ढूंढना है।

उदाहरण:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

डायनामिक प्रोग्रामिंग

1. dp[i][j] = (i,j) पर समाप्त होने वाले सभी-1 वर्ग की अधिकतम भुजा लंबाई।
2. यदि matrix[i][j] == '1':
   • dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])।
3. अन्यथा dp[i][j] = 0।
4. अधिकतम dp[i][j] ट्रैक करें, उत्तर = maxSide^2।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (!n) return 0;
        int m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        int maxSide = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) dp[i][j] = 1;
                    else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};

int main() {
    vector<vector<char>> v = {{'1','0','1','0','0'},
                                 {'1','0','1','1','1'},
                                 {'1','1','1','1','1'},
                                 {'1','0','0','1','0'}};
    Solution ob;
    cout << ob.maximalSquare(v); // 4
    return 0;
}

इनपुट

[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

आउटपुट

4