Sponsored
Sponsored
This approach creates a copy of the original board. It calculates the new state for each cell using the current state from the original board while updating the new state in the copy. Once all cells have been processed, it updates the original board with the calculated states from the copy.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, because each cell is visited once.
Space Complexity: O(m * n), due to the additional copy of the board.
1#include <vector>
2using namespace std;
3
4void gameOfLife(vector<vector<int>>& board) {
5 int m = board.size(), n = board[0].size();
6 vector<vector<int>> copy = board;
7 vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
8
9 for (int i = 0; i < m; i++) {
10 for (int j = 0; j < n; j++) {
11 int liveNeighbors = 0;
12 for (auto d : directions) {
13 int ni = i + d.first, nj = j + d.second;
14 if (ni >= 0 && ni < m && nj >= 0 && nj < n && copy[ni][nj] == 1) {
15 liveNeighbors++;
16 }
17 }
18
19 if (copy[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
20 board[i][j] = 0;
21 } else if (copy[i][j] == 0 && liveNeighbors == 3) {
22 board[i][j] = 1;
23 }
24 }
25 }
26}
27The C++ solution follows a similar approach to the C version, using a temporary board to store the current state. It utilizes STL vectors and iterates over all cells, checking live neighbors from eight possible directions. Once the next state is computed for all cells, the original board is updated.
This approach uses in-place updates by leveraging different state values. We introduce temporary states: 2 represents a cell that was originally live (1) but will be dead in the next state, and -1 represents a cell that was dead (0) but will be live in the next state. At the end, these temporary states are converted to the final states.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1), as no additional space is used beyond input storage.
1 public void GameOfLife(int[][] board) {
int m = board.Length, n = board[0].Length;
int[] directions = {-1, 0, 1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int liveNeighbors = 0;
foreach (int dx in directions) {
foreach (int dy in directions) {
if (dx == 0 && dy == 0) continue;
int ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && Math.Abs(board[ni][nj]) == 1) {
liveNeighbors++;
}
}
}
if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
board[i][j] = 2;
else if (board[i][j] == 0 && liveNeighbors == 3)
board[i][j] = -1;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == -1) {
board[i][j] = 1;
} else if (board[i][j] == 2) {
board[i][j] = 0;
}
}
}
}
}
C# leans on temporal discrete float values to institute direct state traversal occupations otherwise printed through implicit copying in data arrays, leading to a succinct mechanism collapsing multiple operational cycles.