ধরুন আমাদের একটি 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 :=ম্যাট্রিক্সের কলাম সংখ্যা
-
আকারের একটি 2D অ্যারে ডিপি (n x m) সংজ্ঞায়িত করুন এবং 1
দিয়ে পূরণ করুন -
ret :=1
-
আরম্ভ করার জন্য i :=n - 1, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), করুন −
-
j শুরু করার জন্য :=m - 1, যখন j>=0, আপডেট করুন (j 1 দ্বারা কম করুন), −
-
val :=inf
-
যদি i + 1
-
val :=সর্বনিম্ন dp[i + 1, j] এবং val
-
-
অন্যথায়
-
val :=0
-
-
যদি j + 1
-
val :=সর্বনিম্ন dp[i, j + 1] এবং val
-
-
অন্যথায়
-
val :=0
-
-
যদি i + 1
-
val :=সর্বনিম্ন dp[i + 1, j + 1] এবং val
-
-
অন্যথায়
-
val :=0
-
-
যদি val inf এর মত হয়, তাহলে −
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
dp[i, j] :=dp[i, j] + val
-
ret :=ret এবং dp[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
