สมมติว่ามีห้องขัง 8 ห้องติดต่อกัน และแต่ละห้องขังมีนักโทษหรือห้องขังว่างเปล่า ในแต่ละวัน ไม่ว่าห้องขังจะว่างหรือห้องว่างจะเปลี่ยนแปลงตามกฎต่อไปนี้ −
-
หากเซลล์หนึ่งมีเพื่อนบ้านติดกันสองคนซึ่งว่างทั้งคู่หรือว่างทั้งสอง เซลล์นั้นจะถูกครอบครอง
-
มิฉะนั้นจะว่างเปล่า
เราจะอธิบายสถานะปัจจุบันของเรือนจำด้วยวิธีต่อไปนี้:เซลล์[i] จะเป็น 1 หากเซลล์ที่ i ถูกครอบครอง มิฉะนั้น เซลล์[i] จะเป็น 0
ดังนั้นเราจึงมีสถานะเริ่มต้นของเรือนจำ จากนั้นคืนสถานะของเรือนจำหลังจาก N วัน
ดังนั้นหากอินพุตมีลักษณะดังนี้:[0,1,0,1,1,0,0,1] และ N =7 ผลลัพธ์จะเป็น [0,0,1,1,1,0,0,0, 0]. นี่เป็นเพราะสิ่งต่อไปนี้ เป็นเวลาเจ็ดวัน −
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
-
สร้างอาร์เรย์ที่เรียกว่า temp ขนาด 8
-
สำหรับ j ในช่วง 1 ถึง 6
-
ถ้าเซลล์[j – 1] XOR เซลล์[j + 1] =0 แล้ว temp[j] :=1
-
-
เซลล์ :=อุณหภูมิ
-
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]
