সমস্যা বিবরণ
একটি ২D ম্যাট্রিক্স দেওয়া আছে। আমাদের কাজ হলো সর্ববড় 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 := কলাম সংখ্যা।dp[n][m]অ্যারে তৈরি করুন এবং সব জায়গায়1দিয়ে ফিল করুন।ret := 1ইনিশিয়ালাইজ করুন।- ম্যাট্রিক্সকে নিচে থেকে উপরে এবং ডান থেকে বামে ট্রভার্স করুন (রিভার্স অর্ডার)।
- প্রতিটি সেল
(i, j)এর জন্য নিচ, ডান এবং ডায়াগোনাল নিচ-ডান সেলগুলো চেক করুন যাতে একই মান থাকে। - যদি সমান থাকে, তবে
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])। ret-কে সর্বোচ্চ মানের সাথে আপডেট করুন।- শেষে
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 main() {
vector<vector<int>> matrix = {
{1, 1, 8, 3},
{1, 5, 5, 5},
{2, 5, 5, 5},
{4, 5, 5, 5}
};
cout << solve(matrix);
return 0;
}
ইনপুট ও আউটপুট
ইনপুট: {{1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5, 5}}
আউটপুট: 3
