ধরা যাক একটি 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
সমাধানের ধাপগুলো −
ans := 0, n := সারি সংখ্যা, c := কলাম সংখ্যা
যদি n 0 হয়, তবে 0 রিটার্ন করব
(n x c) আকারের অন্য একটি ম্যাট্রিক্স তৈরি করব
i = 0 থেকে n-1 পর্যন্ত
j = 0 থেকে c-1 পর্যন্ত
m[i, j] := matrix[i, j]
ans := 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]-এর মিনিমাম
ans := m[i, j] এবং ans-এর ম্যাক্সিমাম
ans*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
