ধরুন আমাদের একটি 2D বাইনারি ম্যাট্রিক্স আছে যা 0 এবং 1 দিয়ে ভরা। আমাদের সবচেয়ে বড় বর্গ খুঁজে বের করতে হবে যেখানে শুধুমাত্র 1 আছে এবং এর ক্ষেত্রফল ফেরত দিতে হবে। তাই ম্যাট্রিক্স যদি −
এর মত হয়| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
তাহলে আউটপুট হবে 4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=0, n :=সারির সংখ্যা, c :=সারির সংখ্যা
-
যদি n 0 হয়, তাহলে 0 ফেরত দিন
-
অর্ডারের আরেকটি ম্যাট্রিক্স তৈরি করুন (n x c)
-
0 থেকে n – 1
রেঞ্জের i জন্য-
j-এর জন্য 0 থেকে c – 1
পরিসরে-
m[i, j] :=ম্যাট্রিক্স[i, j]
-
উত্তর :=সর্বাধিক m[i, j] এবং ans
-
-
-
j-এর জন্য 0 থেকে c – 1
পরিসরে-
যদি m[i, j] 0 না হয়, তাহলে
-
m[i, j] :=1 + সর্বনিম্ন m[i + 1, j], m[i, j-1], m[i + 1, j-1],
-
-
উত্তর :=সর্বাধিক m[i, j] এবং ans
-
-
উত্তর*উত্তর
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int ans = 0;
int n = matrix.size();
if(!n)return 0;
int c = matrix[0].size();
vector<vector<int>> m(n, vector <int> (c));
for(int i =0;i<n;i++){
for(int j = 0; j<c;j++){
m[i][j] = matrix[i][j] - '0';
ans = max(m[i][j],ans);
}
}
for(int i =n-2;i>=0;i--){
for(int j =1;j<c;j++){
if(m[i][j]){
m[i][j] = 1 + min({m[i+1][j],m[i][j-1],m[i+1][j-1]});
}
ans = max(ans,m[i][j]);
}
}
return ans*ans;
}
};
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)));
} ইনপুট
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
আউটপুট
4
