Prison Cells After N Days ใน C++

คำอธิบายปัญหา

มีห้องจำคุก 8 ห้องเรียงกัน แต่ละห้องมีผู้ติดคุก (1) หรือว่าง (0) ทุกวันสถานะเปลี่ยนตามกฎ: ห้องจะกลายเป็น 1 ถ้าห้องข้างเคียงทั้งสองเหมือนกัน (ทั้งคู่เป็น 1 หรือทั้งคู่เป็น 0) มิฉะนั้นเป็น 0 ต้องการหาสถานะหลังจาก N วัน

ตัวอย่าง: [0,1,0,1,1,0,0,1], N=7 → [0,0,1,1,0,0,0,0]

ข้อสังเกตสำคัญ

เนื่องจากมีเพียง 8 ห้อง สถานะที่เป็นไปได้มีสูงสุด 2⁸ = 256 แบบ จะต้องมี cycle เกิดขึ้น ระยะของ cycle สูงสุด 14 วัน (จากการทดลอง)

วิธีแก้ปัญหา

1. จำลอง 14 วันแรก บันทึกสถานะแต่ละวัน
2. หาก N > 14 ใช้ N % 14 (ถ้าหารลงตัวใช้วันที่ 14)

ตัวอย่างโค้ด C++

#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] << (i+1 < v.size() ? ", " : "");
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        map<int, vector<int>> m;
        if(N == 0) return cells;
        
        for(int day = 1; day <= 14; day++) {
            vector<int> temp(8, 0);
            for(int j = 1; j < 7; j++) {
                if(cells[j-1] == cells[j+1]) temp[j] = 1;
            }
            cells = temp;
            m[day] = temp;
        }
        
        int idx = N % 14;
        if(idx == 0) idx = 14;
        return m[idx];
    }
};

int main() {
    vector<int> v1 = {0,1,0,1,1,0,0,1};
    Solution ob;
    print_vector(ob.prisonAfterNDays(v1, 7));
    return 0;
}

อินพุต

[0,1,0,1,1,0,0,1] 7

เอาต์พุต

[0,0,1,1,0,0,0,0]