细菌的繁殖与扩散

GitHub跳转原题关系图返回列表

每天从旧培养皿向新培养皿分配细菌，中心格得两份且八邻格各得一份。

OJ: noi_openjudge

题目 ID: ch0108-15

难度:入门

标签:矩阵模拟python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

九宫格培养皿中心初始有 mm 个细菌，每天每个细菌在原格留下两个后代、向八邻格各扩散一个，输出 nn 天后分布。

思路

每一天新建全零的 following，遍历旧矩阵，将当前格数量的两倍加回原格、同样数量加到八个邻格。全部旧格处理完后再替换状态。

代码

Python代码

python
initial_count, days = map(int, input().split())
current = [[0] * 9 for _ in range(9)]
current[4][4] = initial_count

for _ in range(days):
    following = [[0] * 9 for _ in range(9)]
    for row in range(9):
        for column in range(9):
            count = current[row][column]
            if count == 0:
                continue
            following[row][column] += 2 * count
            for dx in (-1, 0, 1):
                for dy in (-1, 0, 1):
                    if (dx, dy) != (0, 0):
                        following[row + dx][column + dy] += count
    current = following

for row in current:
    print(*row)

C++代码

cpp
#include <cstdio>
#include <cstring>

int a[5][10][10];
int m,n;
int fx[8][2] = {
    1,0,
    0,1,
    -1,0,
    0,-1,
    1,1,
    1,-1,
    -1,-1,
    -1,1
};

void init(){
    scanf("%d%d",&m,&n);
    a[0][5][5] = m;
}

void g(int x,int i,int j,int cnt){
    int i1,i2;
    for (i1=0;i1<8;i1++){
        int nx = i +fx[i1][0];
        int ny = j +fx[i1][1];
        a[x][nx][ny] += cnt;
    }
    a[x][i][j] +=2*cnt;
}

void zeng(int x){
    int i,j;
    for (i=1;i<=9;i++){
        for (j=1;j<=9;j++){
            if( a[x-1][i][j]){
                g(x,i,j,a[x-1][i][j]);
            }
        }
    }
}
int main(){
    init();
    int i,j;
    for(i=1;i<=n;i++){
        zeng(i);
    }
    
    for (i=1;i<=9;i++){
        for (j=1;j<=9;j++){
            printf("%d ",a[n][i][j]);
        }
        printf("\n");
    }
    return 0;
}

复杂度

培养皿固定为 9×99\times9、天数至多 44，时间和空间复杂度均为 O(1)O(1)。

总结

扩散模拟必须以旧状态生成新状态，避免同一天内重复扩散。