मान लीजिए एक पंक्ति में 8 प्रिजन सेल्स हैं, और प्रत्येक सेल में एक कैदी है या वह खाली है। प्रत्येक दिन, सेल के कब्जे या खाली होने की स्थिति निम्न नियमों के अनुसार बदलती है:
यदि एक सेल के दो आसन्न पड़ोसी दोनों कब्जे वाले हैं या दोनों खाली हैं, तो सेल कब्जे वाला हो जाता है।
अन्यथा, यह खाली हो जाता है।
हम प्रिजन की वर्तमान स्थिति को इस तरह वर्णित करेंगे: cells[i] 1 होगा यदि i-वीं सेल कब्जे वाली है, अन्यथा 0।
हमें प्रिजन की प्रारंभिक स्थिति दी गई है, फिर N दिनों के बाद प्रिजन की स्थिति लौटानी है।
उदाहरण के लिए, यदि इनपुट [0,1,0,1,1,0,0,1] है और N = 7, तो आउटपुट [0,0,1,1,0,0,0,0] होगा।
समाधान दृष्टिकोण
एक मैप m और एक विजिटेड सेट बनाएं
यदि N=0 तो cells लौटाएं
14 दिनों तक सिमुलेशन चलाएं (चक्र 14 दिनों का होता है)
प्रत्येक दिन के लिए नया स्टेट temp बनाएं
j=1 से 6 तक: यदि cells[j-1] XOR cells[j+1] == 0 तो temp[j] = 1
N % 14 के आधार पर परिणाम लौटाएं (0 होने पर 14वां दिन)
C++ कार्यान्वयन
#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];
}
};
int main(){
vector<int> v1 = {0,1,0,1,1,0,0,1};
Solution ob;
print_vector(ob.prisonAfterNDays(v1, 7));
return 0;
}
इनपुट
[0,1,0,1,1,0,0,1] 7
आउटपुट
[0,0,1,1,0,0,0,0]
