github倉庫：https://github.com/lzed/leetcode
給出一個矩陣的一個狀態，根據一定規則來計算下一個狀態。
新開一個數組來獲得下一個狀態即可，這樣可以保證狀態互不干擾。
要更新一個位置
那么，一共只有4種轉化（1代表Live，0代表dead）
于是，在對
最后統計結果的時候，我們再對上述關系進行逆映射來得到最后結果。
algorithm 1
class Solution {public: int judge(int x, int y, vector<vector<int>>& a) { int cnt = 0; for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { if (!i && !j) continue; int nx = x + i, ny = y + j; if (nx >= 0 && nx < a.size() && ny >= 0 && ny < a[0].size()) { if (a[nx][ny]) cnt++; } } } return cnt; } void gameOfLife(vector<vector<int>>& board) { int m = board.size(); if (m) { int n = board[0].size(); vector<vector<int>> a(board.size(), vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int t = judge(i, j, board); if (board[i][j]) { if (t < 2) a[i][j] = 0; else if (t == 2 || t == 3) a[i][j] = 1; else a[i][j] = 0; } else { if (t == 3) a[i][j] = 1; else a[i][j] = 0; } } } board = a; } }};algorithm 2
class Solution {public: int f(int x, int y) { if (!x && !y) return 2; if (!x && y) return 3; if (x && !y) return 4; return 5; } int g_PRe(int s) { if (s == 1 || s == 0) return s; if (s == 2 || s == 3) return 0; return 1; } int g_now(int s) { if (s == 1 || s == 0) return s; if (s == 2 || s == 4) return 0; return 1; } int judge(int x, int y, vector<vector<int>>& a) { int cnt = 0; for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { if (!i && !j) continue; int nx = x + i, ny = y + j; if (nx >= 0 && nx < a.size() && ny >= 0 && ny < a[0].size()) { if (g_pre(a[nx][ny])) cnt++; } } } return cnt; } void gameOfLife(vector<vector<int>>& board) { int m = board.size(); if (m) { int n = board[0].size(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int t = judge(i, j, board); if (board[i][j]) { if (t < 2 || t >= 4) board[i][j] = f(1, 0); else board[i][j] = f(1, 1); } else { if (t == 3) board[i][j] = f(0, 1); else board[i][j] = f(0, 0); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) board[i][j] = g_now(board[i][j]); } } }};新聞熱點
疑難解答
