C++でN日後の独房

連続して8つの独房があり、各独房に囚人がいるか、空であるとします。毎日、セルが占有されているか空いているかは、次のルールに従って変化します-

• 1つのセルに2つの隣接するセルがあり、両方が占有されているか、両方が空である場合、そのセルは占有されます。

• それ以外の場合は空になります。

刑務所の現在の状態を次のように説明します。i番目のセルが占有されている場合はcells[i]が1になり、そうでない場合はcells[i]が0になります。

したがって、刑務所の初期状態がわかり、N日後に刑務所の状態に戻ります。

したがって、入力が[0,1,0,1,1,0,0,1]のようで、N =7の場合、出力は[0,0,1,1,0,0,0、 0]。ですから、これは次の理由によるものです。 7日間-

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という名前のセットを1つ作成します。

• Nが0の場合、セルを返します

• 訪問したセットにセルを挿入する

• 1〜14の範囲のiの場合

  • サイズ8のtempという配列を作成します

  • 1〜6の範囲のjの場合

    • cells [j – 1] XOR cells [j + 1] =0の場合、temp [j]：=1

  • セル：=temp

  • m [i]：=temp

  • 訪問者に臨時雇用者を挿入

• 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]