Repository navigation
Expand file tree
/
Copy pathGameOfLife.cpp
More file actions
94 lines (83 loc) · 3.25 KB
/
Copy pathGameOfLife.cpp
File metadata and controls
94 lines (83 loc) · 3.25 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Source : https://leetcode.com/problems/game-of-life/
// Author : Hao Chen
// Date : 2019-03-20
/*****************************************************************************************************
*
* According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular
* automaton devised by the British mathematician John Horton Conway in 1970."
*
* Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell
* interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules
* (taken from the above Wikipedia article):
*
* Any live cell with fewer than two live neighbors dies, as if caused by under-population.
* Any live cell with two or three live neighbors lives on to the next generation.
* Any live cell with more than three live neighbors dies, as if by over-population..
* Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
*
* Write a function to compute the next state (after one update) of the board given its current state.
* The next state is created by applying the above rules simultaneously to every cell in the current
* state, where births and deaths occur simultaneously.
*
* Example:
*
* Input:
* [
* [0,1,0],
* [0,0,1],
* [1,1,1],
* [0,0,0]
* ]
* Output:
* [
* [0,0,0],
* [1,0,1],
* [0,1,1],
* [0,1,0]
* ]
*
* Follow up:
*
* Could you solve it in-place? Remember that the board needs to be updated at the same time:
* You cannot update some cells first and then use their updated values to update other cells.
* In this question, we represent the board using a 2D array. In principle, the board is
* infinite, which would cause problems when the active area encroaches the border of the array. How
* would you address these problems?
*
******************************************************************************************************/
class Solution {
public:
// the problem here is we need store two states in one cell,
// one is the original state, another is the new state
// So, we could store the state into the bit.
// - Old State: the first bit from the right
// - New State: the second bit from the right
void liveCheck(vector<vector<int>>& board, int r, int c) {
int cnt = 0;
for (int i=r-1; i<=r+1; i++) {
if (i < 0 || i>=board.size()) continue;
for (int j=c-1; j<=c+1; j++) {
if (j<0 || j>=board[0].size() || (i==r && j==c)) continue;
if ( board[i][j] & 1 ) cnt++;
}
}
//live -> die
//if (board[r][c]==1 && (cnt < 2 || cnt > 3)) board[r][c] = 1;
//live -> live
if ( board[r][c] == 1 && (cnt == 2 || cnt == 3) ) board[r][c] = 3;
//die -> live
if ( board[r][c] == 0 && cnt == 3 ) board[r][c] = 2;
}
void gameOfLife(vector<vector<int>>& board) {
for (int i=0; i<board.size(); i++) {
for (int j=0; j<board[0].size(); j++) {
liveCheck(board, i, j);
}
}
for (int i=0; i<board.size(); i++) {
for (int j=0; j<board[0].size(); j++) {
board[i][j] >>= 1;
}
}
}
};