A solution using additional spaces to solve a copy of the original board is easy. To get an in-place solution, we need to record the information of state transitions directly in the board.
We record the state transitions as follows:
// States: // 0 : dead to dead // 1 : live to live // 2 : live to dead // 3 : dead to live
The code is as follows.
1 class Solution { 2 public: 3 void gameOfLife(vector<vector<int>>& board) { 4 int m = board.size(), n = m ? board[0].size() : 0; 5 int di[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; 6 int dj[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; 7 for (int i = 0; i < m; i++) { 8 for (int j = 0; j < n; j++) { 9 int live = 0; 10 for (int k = 0; k < 8; k++) { 11 int ii = i + di[k], jj = j + dj[k]; 12 if (ii < 0 || ii >= m || jj < 0 || jj >= n) continue; 13 if (board[ii][jj] == 1 || board[ii][jj] == 2) live++; 14 } 15 if (board[i][j] == 1 && (live < 2 || live > 3)) board[i][j] = 2; 16 else if (!board[i][j] && live == 3) board[i][j] = 3; 17 } 18 } 19 for (int i = 0; i < m; i++) 20 for (int j = 0; j < n; j++) 21 board[i][j] %= 2; 22 } 23 };
Wanna a shorter one? Stefan always does so :-)
