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;
}

和司机:

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 作为数组索引时返回 ArrayOutOfBoundsException。 (循环不“知道”给定 map 右边缘的正方形，它不应该搜索更右边的活着的邻居；这些函数编码了这个事实。)x 和y 只是循环控制变量，用于迭代目标方 block 周围的有效方 block 。

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

我们举个例子。我们将调用 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)。说服自己这些是我们正在调查的广场的邻居，以及广场本身。

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

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