연속으로 8개의 감옥이 있고 각 감옥에 죄수가 있거나 비어 있다고 가정합니다. 매일 다음 규칙에 따라 셀이 비어 있는지 여부가 변경됩니다. -
-
한 셀에 두 개의 인접한 이웃이 있고 둘 다 점유되어 있거나 모두 비어 있으면 해당 셀이 점유됩니다.
-
그렇지 않으면 비어 있게 됩니다.
우리는 감옥의 현재 상태를 다음과 같은 방식으로 설명할 것입니다: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 지도를 만들고 방문이라는 집합을 하나 만듭니다.
-
N이 0이면 셀을 반환합니다.
-
방문한 세트에 셀 삽입
-
범위 1에서 14까지의 i에 대해
-
크기가 8인 temp라는 배열을 만듭니다.
-
범위 1에서 6까지의 j에 대해
-
cells[j – 1] XOR cells[j + 1] =0이면 temp[j] :=1
-
-
세포 :=임시
-
m[i] :=온도
-
방문에 임시 삽입
-
-
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]