289. Game of Life

My naive way is to create a new matrix to compute the updated board. And then dump the values from the new matrix to the board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int rows = board.size();  
5:      int cols = board[0].size();  
6:      vector<vector<int>> res(rows, vector<int>(cols, 0));  
7:      for (int i = 0; i < rows; i++) {  
8:        for (int j = 0; j < cols; j++) {  
9:          int lives = 0;  
10:          for (int ii = max(0, i-1); ii <= min(rows-1, i+1); ii++) {  
11:            for (int jj = max(0, j-1); jj <= min(cols-1, j+1); jj++) {  
12:              if ((ii != i || jj != j) && board[ii][jj] == 1) lives++;  
13:            }  
14:          }  
15:          if (lives < 2 || lives > 3) res[i][j] = 0;  
16:          else if (lives == 3) res[i][j] = 1;  
17:          else res[i][j] = board[i][j];  
18:        }  
19:      }  
20:      for (int i = 0; i < rows; i++) {  
21:        for (int j = 0; j < cols; j++) {  
22:          board[i][j] = res[i][j];  
23:        }  
24:      }  
25:    }  
26:  };  

The top voted solution updates the board in position. Since the life in the board is actually just one bit. We can use the second bit for the update state and make a one right shift to get the updated board.

1:  class Solution {  
2:  public:  
3:    void gameOfLife(vector<vector<int>>& board) {  
4:      int row = board.size();  
5:      if (row == 0) return;  
6:      int col = board[0].size();  
7:      if (col == 0) return;  
8:      vector<pair<int,int>> dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};  
9:      for (int i = 0; i < row; i++) {  
10:        for (int j = 0; j < col; j++) {  
11:          int lives = 0;  
12:          for (int d = 0; d < dir.size(); d++) {  
13:            int ii = i + dir[d].first;  
14:            int jj = j + dir[d].second;  
15:            if (ii < 0 || ii == row || jj < 0 || jj == col) continue;  
16:            if ((board[ii][jj] & 0x1) == 1) lives++;  
17:          }  
18:          if ((board[i][j] & 0x1)== 0 && lives == 3) {  
19:            board[i][j] |= 0x2;  
20:          } else if (lives == 2 || lives == 3) {  
21:            board[i][j] |= board[i][j] << 1;  
22:          }  
23:        }  
24:      }  
25:      for (int i = 0; i < row; i++) {  
26:        for (int j = 0; j < col; j++) {  
27:          board[i][j] >>= 1;  
28:        }  
29:      }  
30:    }  
31:  };