算法标签：

模拟

题解：

题目分析

问题背景：生物学家通过修改细菌 DNA 使其对周围种群密度敏感，培养皿为 20x20 的方格，每个方格种群密度用 0 到 3 表示，DNA 信息由长度为 16 的数组 D 表示。

模拟规则：对于培养皿中的每个方格，其周围上下左右四个方格（边界外视为密度 0）和自身的密度之和为 K，次日该方格密度变化量为 D[K]，且密度需保持在 0 到 3 之间。

输入内容：第一行为模拟天数；第二行为 16 个整数表示的 DNA 规则数组 D；后续 20 行每行 20 个整数表示培养皿的初始种群密度。

输出要求：输出 20 行，每行 20 个字符，根据最终种群密度用 '.'、'!'、'X'、'#' 分别表示密度 0、1、2、3。

解题思路

数据读取：使用 cin 依次读取模拟天数、DNA 规则数组 D 和培养皿的初始种群密度，存储在相应的数组中。

模拟过程： 外层循环根据模拟天数进行迭代。 在每次迭代中，先计算每个方格的 K 值（即周围及自身密度之和），存储在 sum 数组中。 然后根据 D[sum[i][j]] 更新每个方格的种群密度 mat[i][j]，并确保密度在 0 到 3 之间。 结果输出：遍历最终的种群密度数组 mat，根据密度值选择对应的字符 ch[mat[i][j]]，使用 cout 输出 20 行，每行 20 个字符，实现结果的可视化展示。

#include <iostream>
using namespace std;

const int SIZE = 20;
int D[SIZE + 4], mat[SIZE + 4][SIZE + 4], sum[SIZE + 4][SIZE + 4];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char ch[4] = {'.', '!', 'X', '#'};

int main()
{
    int days;
    // 使用 cin 读取要模拟的天数
    cin >> days;

    for (int i = 0; i < 16; ++i)
        // 使用 cin 读取 DNA 规则数组 D 的元素
        cin >> D[i];

    for (int i = 0; i < SIZE; ++i)
        for (int j = 0; j < SIZE; ++j)
            // 使用 cin 读取培养皿初始种群密度
            cin >> mat[i][j];

    while (days--) {
        for (int i = 0; i < SIZE; ++i)
            for (int j = 0; j < SIZE; ++j) {
                sum[i][j] = mat[i][j];
                for (int k = 0; k < 4; ++k) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= SIZE || nx < 0 || ny >= SIZE || ny < 0)
                        continue;
                    sum[i][j] += mat[nx][ny];
                }
            }

        for (int i = 0; i < SIZE; ++i)
            for (int j = 0; j < SIZE; ++j) {
                mat[i][j] += D[sum[i][j]];
                mat[i][j] = max(mat[i][j], 0);
                mat[i][j] = min(mat[i][j], 3);
            }
    }
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            // 使用 cout 输出对应字符
            cout << ch[mat[i][j]];
        }
        // 使用 cout 换行
        cout << endl;
    }
    return 0;
}

✅ 解题思路

📌 状态表示：

使用两个 $20 \times 20$ 的二维数组：

cur[y][x] 表示当前密度；

next[y][x] 表示下一天的新密度。

📌 每天的更新逻辑：

对于每个格子 $(x, y)$，进行如下操作：

计算 $K = cur[y][x] + cur[y-1][x] + cur[y+1][x] + cur[y][x-1] + cur[y][x+1]$；

注意边界处理，超出 $[0, 19]$ 的邻格视为密度 $0$；

计算新的密度 $= cur[y][x] + D[K]$；

使用 min(3, max(0, 新密度)) 限制密度范围；

用 next[y][x] 存储结果；

每天结束后将 next 拷贝回 cur 继续下一天模拟。

📌 输出字符：

使用数组映射：

cpp 复制 编辑 char symbol[] = {'.', '!', 'X', '#'}; ✅ 时间复杂度分析

每天更新所有 $400$ 个格子；

总共 $T$ 天；

总时间复杂度为 $O(T \times 400)$，约 $4 \times 10^4$ 次操作，运行快速。

代码实现：

//sep9
#include <iostream>
using namespace std;
const int SIZE=20;
int D[SIZE+4],mat[SIZE+4][SIZE+4],sum[SIZE+4][SIZE+4];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
char ch[4]={'.','!','X','#'};
int main()
{
    int days;
    scanf("%d",&days);
    
    for(int i=0;i<16;++i)
        scanf("%d",&D[i]);    
    for(int i=0;i<SIZE;++i)
        for(int j=0;j<SIZE;++j)
            scanf("%d",&mat[i][j]);    
    
    while(days--){
        for(int i=0;i<SIZE;++i)
            for(int j=0;j<SIZE;++j){
                sum[i][j]=mat[i][j];
                for(int k=0;k<4;++k){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx>=SIZE||nx<0||ny>=SIZE||ny<0)
                        continue;
                    sum[i][j]+=mat[nx][ny];    
                }
            }
        
        for(int i=0;i<SIZE;++i)
            for(int j=0;j<SIZE;++j){
                mat[i][j]+=D[sum[i][j]];
                mat[i][j]=max(mat[i][j],0);
                mat[i][j]=min(mat[i][j],3);
            }
    }
    for(int i=0;i<SIZE;++i){
        for(int j=0;j<SIZE;++j){
            printf("%c",ch[mat[i][j]]);    
        }
        puts("");    
    }
    return 0;
}