Các tế bào tù sau N ngày trong C ++

Giả sử có 8 ô giam liên tiếp và trong mỗi ô có một tù nhân hoặc ô trống. Trong mỗi ngày, việc ô bị chiếm hoặc bỏ trống sẽ thay đổi theo các quy tắc sau -

• Nếu một ô có hai hàng xóm liền kề đều bị chiếm hoặc cả hai đều bị bỏ trống, thì ô đó sẽ bị chiếm.

• Nếu không, nó sẽ trống.

Chúng tôi sẽ mô tả trạng thái hiện tại của nhà tù theo cách sau:các ô [i] sẽ là 1 nếu ô thứ i bị chiếm, các ô khác [i] sẽ là 0.

Vì vậy, chúng ta có trạng thái ban đầu của nhà tù, sau đó trả lại trạng thái của nhà tù sau N ngày.

Vì vậy, nếu đầu vào là:[0,1,0,1,1,0,0,1] và N =7, thì đầu ra sẽ là [0,0,1,1,0,0,0, 0]. Vì vậy, đây là vì những điều sau đây. Trong bảy ngày -

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]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một bản đồ m và tạo một tập hợp được gọi là đã thăm.

• nếu N là 0, thì trả về các ô

• chèn các ô vào tập hợp đã truy cập

• cho tôi trong phạm vi từ 1 đến 14

  • tạo một mảng được gọi là tạm thời có kích thước 8

  • cho j trong phạm vi từ 1 đến 6

    • nếu ô [j - 1] ô XOR [j + 1] =0, thì temp [j]:=1

  • ô:=temp

  • m [i]:=temp

  • chèn tạm thời vào đã truy cập

• nếu N chia hết cho 14 thì trả về m [14], ngược lại m [N mod 14]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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];
   }
};
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]