हमें एक वर्ग मैट्रिक्स दिया गया है जिसमें केवल 0 और 1 हैं। 0 खाली स्थान दर्शाता है और 1 बाधा दर्शाता है। हमें खाली सेल पर रखे जा सकने वाले दर्पणों की संख्या ढूंढनी होगी ताकि ये दर्पण प्रकाश को नीचे से दाएं स्थानांतरित कर सकें। यह तब संभव है जब, दर्पण इंडेक्स [i,j] पर रखा गया हो और उस विशेष पंक्ति (i) में दाईं ओर के सभी सेल और उस विशेष कॉलम (j) में नीचे के सेल में कोई बाधा न हो।
यदि दर्पण A[i][j] पर है, तो सभी A[i+1 से n][j] और A[i][j+1 से n] खाली हैं यानी 0। जैसा कि नीचे दिए गए चित्र में दिखाया गया है।
इनपुट
Arr[][] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}} आउटपुट
दर्पणों की संख्या: 3
व्याख्या: चित्र में दिखाए अनुसार। दर्पण सेल पर रखे जा सकते हैं:
Arr[1][0] - पंक्ति 1 और कॉलम 0 में इसके नीचे और दाईं ओर सभी 0 हैं।
Arr[2][0] - पंक्ति 2 और कॉलम 0 में इसके नीचे और दाईं ओर सभी 0 हैं।
Arr[4][4] - अंतिम सेल, 0 है और इसके नीचे कोई पंक्ति और दाईं ओर कोई कॉलम नहीं है।
प्रयुक्त दृष्टिकोण
- सरणी Arr[][] का उपयोग 0 और 1 की मैट्रिक्स को दर्शाने के लिए किया जाता है।
- फ़ंक्शन maximumMirror(int mat[][], int n) मैट्रिक्स और इसकी भुजा n को इनपुट के रूप में लेता है और ऊपर दिखाए अनुसार रखे जा सकने वाले अधिकतम दर्पणों की संख्या लौटाता है।
- चर flag का उपयोग arr[i][j] के नीचे के सेल या दाईं ओर के सेल में बाधा की उपस्थिति को चिह्नित करने के लिए किया जाता है।
- Count दर्पणों की संख्या को दर्शाता है, प्रारंभ में 0।
- इंडेक्स 0,0 से मैट्रिक्स को पार करें।
- प्रत्येक सेल के लिए यदि यह खाली है (दर्पण रखा जा सकता है), तो नीचे के सेल (k=i+1 से n-1) की जांच करें। यदि कोई arr[k][j] बाधा है (मान=1) तो while लूप तोड़ें और फ्लैग को 1 के रूप में चिह्नित करें। यदि नहीं, तो दाईं ओर के सेल (l=j+1 से n-1) की जांच जारी रखें।
- बाधा मौजूद होने पर फ्लैग सेट करें।
- दोनों while लूप के बाद यदि फ्लैग 0 है तो count बढ़ाएं क्योंकि दर्पण रखा जा सकता है।
- count को अधिकतम दर्पणों की संख्या के रूप में लौटाएं।
उदाहरण कोड
// C++ प्रोग्राम यह पता लगाने के लिए कि कितने दर्पण प्रकाश को नीचे से दाएं स्थानांतरित कर सकते हैं #include <bits/stdc++.h> using namespace std; // विधि उन दर्पणों की संख्या लौटाती है जो प्रकाश को नीचे से दाएं स्थानांतरित कर सकते हैं int maximumMirror(int mat[5][5], int N){ // चिह्नित करने के लिए कि दाएं या नीचे के सभी सेल 0 हैं---कोई बाधा नहीं int flag=0; int count=0; //दर्पणों की संख्या int i,j,k,l; //सभी सेल के लिए for (int i=0; i आउटपुट
अधिकतम दर्पण जो प्रकाश को नीचे से दाएं स्थानांतरित कर सकते हैं: 3
