C++ में मैट्रिक्स में समान मान वाले k×k सबमैट्रिक्स ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक 2D मैट्रिक्स है, हमें सबसे बड़ा k×k सबमैट्रिक्स ढूंढना है जहां सभी तत्वों का मान समान हो, और फिर k का मान ज्ञात करना है।

उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:

1	1	8	3
1	5	5	5
2	5	5	5
4	5	5	5

तो आउटपुट 3 होगा, क्योंकि मान 5 का एक 3×3 वर्ग सबमैट्रिक्स मौजूद है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

n := मैट्रिक्स की पंक्तियों की संख्या
m := मैट्रिक्स के स्तंभों की संख्या
आकार n×m का एक 2D DP ऐरे परिभाषित करें और इसे 1 से भरें
ret := 1
i := n-1 से 0 तक (घटते क्रम में):
- j := m-1 से 0 तक (घटते क्रम में):
  - val := अनंत
  - यदि i+1 < n और v[i+1][j] == v[i][j], तो val := min(dp[i+1][j], val), अन्यथा val := 0
  - यदि j+1 < m और v[i][j+1] == v[i][j], तो val := min(dp[i][j+1], val), अन्यथा val := 0
  - यदि i+1 < n और j+1 < m और v[i+1][j+1] == v[i][j], तो val := min(dp[i+1][j+1], val), अन्यथा val := 0
  - यदि val अनंत के बराबर है, तो अगले इटरेशन पर जाएं
  - dp[i][j] := dp[i][j] + val
  - ret := max(ret, dp[i][j])
ret वापस करें

उदाहरण

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

class Solution {
public:
    int solve(vector<vector<int>>& v) {
        int n = v.size();
        int m = v[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 1));
        int ret = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int val = INT_MAX;
                if (i + 1 < n && v[i + 1][j] == v[i][j]) 
                    val = min(dp[i + 1][j], val);
                else 
                    val = 0;
                
                if (j + 1 < m && v[i][j + 1] == v[i][j]) 
                    val = min(dp[i][j + 1], val);
                else 
                    val = 0;
                
                if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) 
                    val = min(dp[i + 1][j + 1], val);
                else 
                    val = 0;
                
                if (val == INT_MAX) continue;
                dp[i][j] += val;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
};

int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}

int main() {
    vector<vector<int>> matrix = {
        {1, 1, 8, 3},
        {1, 5, 5, 5},
        {2, 5, 5, 5},
        {4, 5, 5, 5}
    };
    cout << solve(matrix);
}

इनपुट

{{1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5, 5}};