মান লেযিয়ে একটি সারিয়ে ৮টি প্রিজন সেল আছে, প্রতিটি সেলে একটি বন্দি আছে বা খালি। প্রতিদিন, সেলটি দখল করা আছে বা খালি তা নিচের নিয়ম অনুযায়ী পরিবর্তন হয় -
যদি একটি সেলের দুটি প্রতিবেশী উভয়ই দখল করা থাকে বা উভয়ই খালি থাকে, তবে সেলটি দখল করা হয়ে যাবে।
অন্যথায়, সেটি খালি হয়ে যাবে।
প্রিজনের বর্তমান স্টেট এভাবে বর্ণনা করা হয়: cells[i] = 1 যদি i-তম সেল দখল করা থাকে, অন্যথায় 0। প্রাথমিক স্টেট দেওয়া থাকলে, N দিন পর প্রিজনের স্টেট রিটার্ন করতে হবে। ইনপুট [0,1,0,1,1,0,0,1], N = 7 হলে আউটপুট [0,0,1,1,0,0,0,0]। কারণ ৭ দিনের পর Ferry -
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 এবং visited নামক একটি সেট তৈরি করুন
যদি N == 0 হয়, cells রিটার্ন করুন
visited-এ cells ইনসার্ট করুন
i = 1 থেকে 14 পর্যন্ত লুপ চালান
temp নামে ৮ আকারের একটি অ্যারে তৈরি করুন
j = 1 থেকে 6 পর্যন্ত লুপ চালান
যদি cells[j-1] XOR cells[j+1] == 0 হয়, temp[j] := 1
cells := temp
m[i] := temp
visited-এ temp ইনসার্ট করুন
যদি N ১৪ দিয়ে বিভাজ্য হয়, m[14] রিটার্ন করুন, অন্যথায় m[N % 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]
