C++ 实现黄金庭园小画家 Griseo 的绘画扩散问题

Griseo 是黄金庭园的团宠小画家，最近她又开始了她的创作。由于 Griseo 画工强大，所以她只需要在画布（视为 n*m 的二维平面，坐标起始点为 1）的某处点上一笔，颜料就会依照 Griseo 的想法无尽扩散，颜料的扩散方式是这样的：

初始时颜料会向上扩散；
每个小时，颜料会根据 Griseo 的想法扩散 s[i] 的距离；
当该小时结束后，颜料将分裂成两部分，各向 45° 方向移动（颜料必须走过 si 的距离才能向两边分裂）；

Griseo 想知道在每个小时末颜料的覆盖范围，以此推测画作的模样。

输入

第一行包含三个整数 n 、 m 、 t ，代表画布大小（n 行 m 列）和颜料扩散时间；第二行包含 t 个整数 s[i]，代表第 i 个小时颜料扩散的距离；第三行包含两个整数 x、y 代表颜料的初始位置。

输出

输出为一行，包含 t 个整数，第 i 个整数代表第 i 个小时末画布上颜料的覆盖范围。

C++ 代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,t,x,y;
int s[1000005];
bool vis[105][105][105];//vis 数组记录是否被涂过

int main(){
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=t;i++) scanf("%d",&s[i]);
    scanf("%d%d",&x,&y);
    vis[0][x][y]=1;//初始化
    for(int i=1;i<=t;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                if(vis[i-1][j][k]){//如果已经被涂过
                    if(j-s[i]>0&&k+s[i]<=m) vis[i][j-s[i]][k+s[i]]=1;//向右上角移动
                    if(j+s[i]<=n&&k+s[i]<=m) vis[i][j+s[i]][k+s[i]]=1;//向右下角移动
                }
            }
        }
    }
    for(int i=1;i<=t;i++){
        int ans=0;
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                if(vis[i][j][k]) ans++;//统计被涂过的点的个数
            }
        }
        printf("%d ",ans);//输出
    }
    return 0;
}

代码逻辑解释

使用三维数组 vis[i][j][k] 来记录每个小时 i、每个位置 (j, k) 是否被颜料覆盖。
初始化 vis[0][x][y] = 1，表示初始位置被覆盖。
遍历每个小时 i，对于每个已经被覆盖的位置 (j, k)，根据扩散距离 s[i] 向右上角和右下角移动，并更新 vis 数组。
统计每个小时末被覆盖的位置数量，即为该小时末颜料的覆盖范围。

总结

以上代码实现了 Griseo 的绘画扩散问题，通过遍历和更新 vis 数组来模拟颜料的扩散过程，最终输出每个小时末颜料的覆盖范围。