हमें एक वर्ग मैट्रिक्स दिया गया है जिसमें केवल 0 और 1 हैं। 0 एक खाली खाली जगह का प्रतिनिधित्व करता है और 1 का मतलब बाधा है। हमें ऐसे कई दर्पण खोजने होंगे, जिनमें अटेम्प्टी सेल इस प्रकार रखे जा सकें कि ये दर्पण नीचे से दाईं ओर प्रकाश स्थानांतरित कर सकें। यह तब संभव है, जब मिरर को इंडेक्स [i,j] पर रखा जाता है और उस विशेष पंक्ति (i) में दाईं ओर के सभी सेल्स के लिए और उस विशेष कॉलम में सबसे नीचे ( j ) के सेल में कोई बाधा नहीं होती है।
यदि दर्पण A[i][j] पर है, तो सभी A[i+1 to n][ j ] और A[i][j+1 to 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}} आउटपुट
No. of mirrors : 3
स्पष्टीकरण - जैसा कि चित्र में दिखाया गया है। दर्पणों को कक्षों में रखा जा सकता है
Arr[1][0] - पंक्ति 1 और कॉलम 0 में सभी 0 नीचे और दाईं ओर हैं।
Arr[2][0] - पंक्ति 2 और कॉलम 0 में सभी 0 नीचे और दाईं ओर हैं।
Arr[4][4] - अंतिम सेल, 0 है और नीचे कोई पंक्ति नहीं है और दाईं ओर कॉलम है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
Array Arr[][] का उपयोग 0 और 1 के मैट्रिक्स को दर्शाने के लिए किया जाता है..
-
फंक्शन मैक्सिमममिरर (इंट मैट [] [], इंट एन) इनपुट के रूप में मैट्रिक्स और इसके साइड एन को लेता है और ऊपर दिखाए गए अनुसार रखे जा सकने वाले अधिकतम दर्पणों की संख्या देता है।
-
वेरिएबल फ़्लैग का इस्तेमाल नीचे के सेल या एरर [i] [j] के दायीं ओर के सेल में एक बाधा की उपस्थिति को चिह्नित करने के लिए किया जाता है।
-
काउंट का उपयोग दर्पणों की संख्या को दर्शाने के लिए किया जाता है, प्रारंभ में 0 ।
-
इंडेक्स 0,0 से ट्रैवर्स मैट्रिक्स।
-
प्रत्येक सेल के लिए यदि यह खाली है (दर्पण रखा जा सकता है), नीचे की कोशिकाओं की जांच करें (k=i+1 to n-1) । यदि कोई arr[k][j] एक बाधा है (मान=1 ) तो ब्रेक करते समय लूप और ध्वज को 1 के रूप में चिह्नित करें। यदि नहीं, तो दाईं ओर (l=j+1 से n-1) कक्षों की जांच जारी रखें।
-
बाधा होने पर ध्वज सेट करें।
-
दोनों समय लूप के बाद यदि ध्वज 0 है तो वृद्धि की गणना दर्पण के रूप में रखी जा सकती है।
-
संख्या के रूप में वापसी गिनती। दर्पणों का जो अधिकतम है।
उदाहरण
// C++ program to find how many mirrors can transfer
// light from bottom to right
#include <bits/stdc++.h>
using namespace std;
// method returns number of mirror which can transfer
// light from bottom to right
int maximumMirror(int mat[5][5], int N){
// to mark that all cells in the right or bottom are 0---no obstacle
int flag=0;
int count=0; //count of mirrors
int i,j,k,l;
//for all cells
for (int i=0; i<N; i++)
for(j=0;j<N;j++){
//check from next column and next row
int k=i+1;
int l=j+1;
if(mat[i][j]==0) //position for mirror{
while(k<N) //check for rows below{
if(mat[k][j]==1) //keeping column fixed, if there is obstacle break{
flag=0; break; }
else
flag=1;
k++;
}
if(flag==1) //if no obstacle in rows then check columns in right
while(l<N) //checking for columns in right{
if(mat[i][l]==1) //keep row fixed, if obstacle break{
flag=0; break;
}
else
flag=1;
l++;
}
if(flag==1) //there is no obstacle for mirror mat[i][j]
count++;
}
}
return count;
}
int main(){
int N = 5;
//matrix where 1 represents obstacle form 5X5 matrix
int mat[5][5] = {{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}};
cout <<"Maximum mirrors which can transfer light from bottom to right :"<<
maximumMirror(mat, N) << endl;
return 0;
} आउटपुट
Maximum mirrors which can transfer light from bottom to right :3