এই সমস্যায়, আমাদের একটি ২D ম্যাট্রিক্স mat[][] দেওয়া আছে যার আকার n, n একটি বিজোড় সংখ্যা। আমাদের কাজ হলো ম্যাট্রিক্সে বর্গের সর্বোচ্চ পার্শ্ব দৈর্ঘ্য খুঁজে বের করা।
সমস্যা বিবরণ
আমাদের সেই বর্গ ম্যাট্রিক্সের দৈর্ঘ্য বের করতে হবে যার পারিমিটারের সব মান একই এবং যা ম্যাট্রিক্সের সাথে একই কেন্দ্র শেয়ার করে।
উদাহরণ
ইনপুট
mat[][] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
}
আউটপুট
3
সমাধানের পদ্ধতি
একটি সহজ সমাধান হলো ম্যাট্রিক্সের কেন্দ্র বের করা। যেহেতু n বিজোড়, কেন্দ্র (n/2, n/2) ইনডেক্সে থাকবে। কেন্দ্র পাওয়ার পর সেটার চারপাশে সব ২D সাব-ম্যাট্রিক্স চেক করব যেন তাদের সব পারিমিটার মান একই হয়।
কেন্দ্র থেকে i দূরত্বে থাকা সাব-ম্যাট্রিক্সের পারিমিটারে থাকবে (n/2 - i) এবং (n/2 + i) সারি ও কলামের উপাদান। আমরা i = 0 থেকে n/2 পর্যন্ত চেক করব কোন সাব-ম্যাট্রিক্সের সব পারিমিটার এলিমেন্ট একই কিনা।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
#define n 5
using namespace std;
int findMaxSideSquare(int matrix[][n]) {
int squareLen = 1;
for (int i = 0; i < n / 2; i++) {
int sideVal = matrix[i][i];
bool isSquare = true;
for (int j = i; j < n - i; j++) {
if (matrix[i][j] != sideVal)
isSquare = false;
if (matrix[n - i - 1][j] != sideVal)
isSquare = false;
if (matrix[j][i] != sideVal)
isSquare = false;
if (matrix[j][n - i - 1] != sideVal)
isSquare = false;
}
if (isSquare)
squareLen = n - 2 * i;
}
return squareLen;
}
int main() {
int mat[n][n] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
};
cout << "The maximum side length of square in a Matrix is " << findMaxSideSquare(mat);
return 0;
}
আউটপুট
The maximum side length of square in a Matrix is 3
