मान लीजिए कि हमारे पास 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 :=मैट्रिक्स की पंक्ति गणना
-
मी :=मैट्रिक्स की कॉलम संख्या
-
एक 2D सरणी dp आकार (n x m) परिभाषित करें और 1
. से भरें -
रिट :=1
-
इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें-
प्रारंभ करने के लिए j :=m-1, जब j>=0, अद्यतन करें (j को 1 से घटाएं), करें -
-
वैल:=inf
-
यदि i + 1
-
वैल:=न्यूनतम डीपी[i + 1, j] और वैल
-
-
अन्यथा
-
वैल:=0
-
-
यदि j + 1
-
वैल:=न्यूनतम डीपी[i, j + 1] और वैल
-
-
अन्यथा
-
वैल:=0
-
-
यदि i + 1
-
वैल:=न्यूनतम डीपी[i + 1, j + 1] और वैल
-
-
अन्यथा
-
वैल:=0
-
-
अगर वैल inf के समान है, तो -
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
डीपी [आई, जे]:=डीपी [आई, जे] + वैल
-
रिट :=अधिकतम रिट और डीपी[i, j]
-
-
-
-
वापसी रिट
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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} }; आउटपुट
3
