# 957. Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: `cells[i] == 1` if the `i`-th cell is occupied, else `cells[i] == 0`.

Given the initial state of the prison, return the state of the prison after `N` days (and `N` such changes described above.)

Example 1:

``````Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
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]
``````

Example 2:

``````Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]
``````

Note:

1. `cells.length == 8`
2. `cells[i]` is in `{0, 1}`
3. `1 <= N <= 10^9`

``````class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
vector<int> res;
string str;
for (int num : cells) str += to_string(num);
unordered_map<string, int> m;
while (N > 0) {
m[str] = N--;
string cur(8, '0');
for (int i = 1; i < 7; ++i) {
cur[i] = (str[i - 1] == str[i + 1]) ? '1' : '0';
}
str = cur;
if (m.count(str)) {
N %= m[str] - N;
}
}
for (char c : str) res.push_back(c - '0');
return res;
}
};
``````

``````class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
map<vector<int>, int> m;
while (N > 0) {
m[cells] = N--;
vector<int> cur(8);
for (int i = 1; i < 7; ++i) {
cur[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
}
cells = cur;
if (m.count(cells)) {
N %= m[cells] - N;
}
}
return cells;
}
};
``````

``````class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
for (N = (N - 1) % 14 + 1; N > 0; --N) {
vector<int> cur(8);
for (int i = 1; i < 7; ++i) {
cur[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
}
cells = cur;
}
return cells;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/957

https://leetcode.com/problems/prison-cells-after-n-days/

https://leetcode.com/problems/prison-cells-after-n-days/discuss/266854/Java%3A-easy-to-understand

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-or-Mod-14

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation