Có 8 ô tù liên tiếp, mỗi ô có tù nhân (1) hoặc trống (0). Mỗi ngày, trạng thái thay đổi: ô có 2 láng giềng cùng chiếm hoặc cùng trống → chiếm, ngược lại → trống. Cho trạng thái ban đầu, tìm trạng thái sau N ngày.
Ví dụ: [0,1,0,1,1,0,0,1], N=7 → [0,0,1,1,0,0,0,0].
Quan sát: trạng thái lặp lại chu kỳ 14 ngày (vì 8 ô, ô đầu/cuối luôn 0 sau ngày 1).
Giải pháp:
Mô phỏng 14 ngày đầu, lưu trạng thái mỗi ngày vào map
Nếu N % 14 == 0 trả về ngày 14, ngược lại ngày N%14
Ví dụ
#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)); }Đầu vào
[0,1,0,1,1,0,0,1] 7
Đầu ra
[0,0,1,1,0,0,0,0]