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