Java: 如何实现康威的生命游戏？

Question

我正在研究康威的生命游戏以自己实现它，并且遇到了以下规则的实现：

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.

和实施（https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation）：

public void gameOfLife(int[][] board) {
    if (board == null || board.length == 0) return;
    int m = board.length, n = board[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int lives = liveNeighbors(board, m, n, i, j);

            // In the beginning, every 2nd bit is 0;
            // So we only need to care about when will the 2nd bit become 1.
            if (board[i][j] == 1 && lives >= 2 && lives <= 3) {  
                board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
            }
            if (board[i][j] == 0 && lives == 3) {
                board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] >>= 1;  // Get the 2nd state.
        }
    }
}

public int liveNeighbors(int[][] board, int m, int n, int i, int j) {
    int lives = 0;
    for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) {
        for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) {
            lives += board[x][y] & 1;
        }
    }
    lives -= board[i][j] & 1;
    return lives;
}

和driver：

public static void main(String args[]) {
    GameOfLife gl = new GameOfLife();

    int[][] board = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0}
            };

    gl.gameOfLife(board);
}

我的问题是，liveNeighbors()中的x和y代表什么？不明白为什么需要Math.min()和Math.max()。还有，lives是否代表棋盘上初始化的生命值？

Answer 1

给定代码使用 min 和 max 函数将搜索限制为数组中的有效条目。如果不这样做，当尝试使用 -1、m 或 n 作为数组索引时，代码将 return 一个 ArrayOutOfBoundsException。（循环不会 "know" 在地图的右边缘给定一个正方形，它不应该搜索更右边的活着的邻居；这些函数编码了这个事实。） x 和 y 只是循环控制变量，用于迭代目标方块周围的有效方块。

至于 lives 变量，这是一个占位符，用于计算下面的循环找到了多少活邻居。您可能已经猜到它是 liveNeighbors 函数的 return 值。

我们来举个例子。我们将调用 liveNeighbors(board,9,9,0,2)，其中 board 是驱动程序中给出的电路板。您的电路板尺寸为 9x9，因此这些是我们通过的 m 和 n，对于我们的示例，我们正在调查 0、2 处的正方形，这是第三行的第一个条目（右边有一个 1）。太好了，让我们开始吧。

i=0，所以x = Math.max(i - 1, 0) = Math.max(-1, 0) = 0（这说明了max函数的原因：如果我们只是说int x=i-1，我们最终会得到x = -1 超出了数组的边界。接下来我们评估 x <= Math.min(i + 1, m - 1) = Math.min(1, 8) = 1。如果我们正在调查一个最后一列中的单元格，此条件将强制执行数组的右边缘。

我将把涉及 y 和 j 的类似逻辑留给你。

循环简化为：

for (int x = 0; x <= 1; x++) {
    for (int y = 1; y <= 3; y++) {
        lives += board[x][y] & 1;
    }
}

内部循环将运行六次，具有以下 (x,y) 对：(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)。说服自己这些是我们正在调查的广场的邻居，以及广场本身。

这六个方块中有五个将 return 0，其中一个位于 (1,2) returning 1，因此在此循环结束时，lives 将等于 1。最后要做的是 lives -= board[i][j] & 1;，如果我们正在调查的方格中有 1，则将 lives 减 1。在我们的例子中它不是 (board[i][j] = 0) 所以我们减去 0，留下 1，我们 return。 liveNeighbors(board,9,9,0,2) = 1

我可能已经将 x 和 y 倒退了一两次，但希望这就足够了，这样您就可以理解发生了什么。

Java: 如何实现康威的生命游戏？

Java: How to implement Conway's Game of Life?

java

algorithm

bit