इस समस्या में, हमें n आकार का एक 2-D मैट्रिक्स mat[][] दिया गया है, 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
समाधान दृष्टिकोण
समस्या का एक सरल समाधान मैट्रिक्स के केंद्र तत्व को ढूंढना है क्योंकि यह एक विषम मैट्रिक्स है, केंद्र तत्व इंडेक्स (एन/2, एन/2) पर होगा। केंद्र खोजने के बाद हम सभी 2 डी उप- इसके चारों ओर मैट्रिसेस जो जांच करेगा कि क्या इसके सभी तत्व समान हैं।
केंद्र से दूर इंडेक्स पर सबमैट्रिक्स में इंडेक्स (एन/2 - 1) से (एन/2 + 1) तक पंक्ति (एन/2 - 1) और (एन/2 + 1) का एक तत्व होगा। इसके परिमाप में सूचकांक (n/2 - 1) से (n/2 + 1) तक कॉलम (n/2 - 1) और (n/2 + 1) के अवयव भी शामिल हैं। हमें यह जांचने की आवश्यकता है कि 0 से n/2 तक के किसी भी मान के लिए उप-मैट्रिक्स में सभी परिधि तत्व समान हैं या नहीं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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है