当前位置: 面试刷题>> 生命游戏(经典算法150题)


题目描述补充

生命游戏(Conway's Game of Life) 是一种零玩家游戏,由数学家约翰·何顿·康威在1970年发明。在这个游戏中,一个二维网格上的每个格子居住着一个细胞,细胞可以是活的(用1表示)或死的(用0表示)。每个细胞与其相邻的八个格子(包括水平、垂直和对角线方向)相互作用。根据以下规则,细胞的状态会在每个时间步更新:

  1. 出生:如果一个死细胞恰好有三个活邻居,则在下一个时间步,该细胞变为活细胞(出生)。
  2. 存活:如果一个活细胞有两个或三个活邻居,则在下一个时间步,该细胞保持活状态(存活)。
  3. 死亡:如果一个活细胞有少于两个或多于三个活邻居,则在下一个时间步,该细胞变为死细胞(死亡)。

游戏从一个初始状态开始,然后按照上述规则不断迭代,直到网格达到一个稳定状态(即,没有细胞的状态会在下一个时间步改变)。

示例代码

以下是使用PHP、Python和JavaScript编写的生命游戏示例代码。

PHP 示例

function countNeighbors($grid, $x, $y, $width, $height) {
    $count = 0;
    for ($dx = -1; $dx <= 1; $dx++) {
        for ($dy = -1; $dy <= 1; $dy++) {
            if ($dx == 0 && $dy == 0) continue;
            $nx = $x + $dx;
            $ny = $y + $dy;
            if ($nx >= 0 && $nx < $width && $ny >= 0 && $ny < $height && $grid[$ny][$nx] == 1) {
                $count++;
            }
        }
    }
    return $count;
}

function nextGeneration($grid, $width, $height) {
    $next = array_fill(0, $height, array_fill(0, $width, 0));
    for ($y = 0; $y < $height; $y++) {
        for ($x = 0; $x < $width; $x++) {
            $neighbors = countNeighbors($grid, $x, $y, $width, $height);
            if ($grid[$y][$x] == 1 && ($neighbors == 2 || $neighbors == 3)) {
                $next[$y][$x] = 1; // Survive
            } elseif ($grid[$y][$x] == 0 && $neighbors == 3) {
                $next[$y][$x] = 1; // Born
            }
        }
    }
    return $next;
}

// 示例初始网格
$grid = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1]
];

// 迭代更新网格
$nextGen = nextGeneration($grid, 3, 3);
print_r($nextGen);

Python 示例

def count_neighbors(grid, x, y, width, height):
    count = 0
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if dx == 0 and dy == 0:
                continue
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height and grid[ny][nx] == 1:
                count += 1
    return count

def next_generation(grid, width, height):
    next_grid = [[0] * width for _ in range(height)]
    for y in range(height):
        for x in range(width):
            neighbors = count_neighbors(grid, x, y, width, height)
            if grid[y][x] == 1 and (neighbors == 2 or neighbors == 3):
                next_grid[y][x] = 1  # Survive
            elif grid[y][x] == 0 and neighbors == 3:
                next_grid[y][x] = 1  # Born
    return next_grid

# 示例初始网格
grid = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1]
]

# 迭代更新网格
next_gen = next_generation(grid, 3, 3)
for row in next_gen:
    print(row)

JavaScript 示例

function countNeighbors(grid, x, y, width, height) {
    let count = 0;
    for (let dx = -1; dx <= 1; dx++) {
        for (let dy = -1; dy <= 1; dy++) {
            if (dx === 0 && dy === 0) continue;
            const nx = x + dx;
            const ny = y + dy;
            if (nx >= 0 && nx < width && ny >= 0 && ny < height && grid[ny][nx] === 1) {
                count++;
            }
        }
    }
    return count;
}

function nextGeneration(grid, width, height) {
    const next = Array.from({ length: height }, () => Array(width).fill(0));
    for (let y = 0; y < height; y++) {
        for (let x = 0; x < width; x++) {
            const neighbors = countNeighbors(grid, x, y, width, height);
            if (grid[y][x] === 1 && (neighbors === 2 || neighbors === 3)) {
                next[y][x] = 1; // Survive
            } else if (grid[y][x] === 0 && neighbors === 3) {
                next[y][x] = 1; // Born
            }
        }
    }
    return next;
}

// 示例初始网格
const grid = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1]
];

// 迭代更新网格
const nextGen = nextGeneration(grid, 3, 3);
console.log(nextGen);

这些示例代码展示了如何根据生命游戏的规则来更新网格的状态。你可以在自己的环境中运行这些代码,并观察网格如何随时间变化。