मान लीजिए कि एक पंक्ति में 8 जेल प्रकोष्ठ हैं, और प्रत्येक कक्ष में एक कैदी है या वह खाली है। प्रत्येक दिन में, चाहे सेल व्यस्त हो या खाली हो, निम्नलिखित नियमों के अनुसार बदल जाता है -
-
अगर एक सेल में दो आसन्न पड़ोसी हैं जो दोनों पर कब्जा कर लिया है या दोनों खाली हैं, तो सेल पर कब्जा हो जाता है।
-
नहीं तो यह खाली हो जाता है।
हम कारागार की वर्तमान स्थिति का वर्णन इस प्रकार करेंगे:यदि i-th कक्ष भरा हुआ है, तो कक्ष [i] 1 होगा, अन्यथा कक्ष [i] 0 होंगे।
तो हमारे पास जेल की प्रारंभिक स्थिति है, फिर एन दिनों के बाद जेल की स्थिति वापस करें।
तो अगर इनपुट इस तरह है:[0,1,0,1,1,0,0,1], और एन =7, तो आउटपुट [0,0,1,1,0,0,0, 0]। तो यह निम्नलिखित के कारण है। सात दिनों के लिए -
Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक नक्शा m बनाएं, और एक सेट बनाएं जिसे विज़िट किया गया कहा जाता है।
-
अगर N 0 है, तो सेल लौटाएं
-
देखे गए सेट में सेल डालें
-
मेरे लिए 1 से 14 की सीमा में
-
आकार 8 का अस्थायी नाम की एक सरणी बनाएं
-
j के लिए 1 से 6 की सीमा में
-
अगर सेल [जे -1] एक्सओआर सेल [जे + 1] =0, तो अस्थायी [जे]:=1
-
-
सेल :=अस्थायी
-
एम [i] :=अस्थायी
-
विज़िट किए गए में अस्थायी डालें
-
-
यदि N 14 से विभाज्य है, तो m[14] लौटाएं, अन्यथा m[N mod 14]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
map <int, vector <int> > m;
if(N == 0) return cells;
set <vector <int> > visited;
visited.insert(cells);
for(int i = 1; i<=14 ; i++ ){
vector <int> temp(8);
for(int j = 1; j < 7; j++){
if(cells[j - 1] ^ cells[j + 1] == 0){
temp[j] = 1;
}
}
cells = temp;
m[i] = temp;
visited.insert(temp);
}
return m[N % 14 == 0? 14 : N % 14];
}
};
main(){
vector<int> v1 = {0,1,0,1,1,0,0,1};
Solution ob;
print_vector(ob.prisonAfterNDays(v1, 7));
} इनपुट
[0,1,0,1,1,0,0,1] 7
आउटपुट
[0,0,1,1,0,0,0,0]