Atcoder ABC460 d 题解

不是说第一个做对的人会有罐头吗？还是说我记错了？

一，题目大意

给一个黑白矩阵,执行以下操作 $10^{100}$ 次：

• 对于白色，若四周八格都有黑，就将其涂为黑。
• 对于黑色，将其涂为白。

求最后矩阵样子。

二，纸上证明

由于操作次数太多，若模拟到世界末日也无法完成，所以我们只从初始状态一步推到最终状态。（即只管起始状态和结果，不管过程的对错）

结论1：初始时，一个颜色为黑且周围八格都为黑的格子，可当作白色格子处理。

由于操作会将当前所有黑色变成白色，会使原本最中间的格子“孤立无援”，易证其要在后续的第奇数操作中才有可能变成黑色。而 $10^{100}$ 次操作为偶数次操作，因此在只管起始状态和结果时，我们可以将其当作白色格子处理。

结论2：该矩阵变化最终陷入长度为2循环，且题目所求的是循环之一。

当矩阵开始变化后，在结论1的前提下，只要有一个黑格子，就会像水波一样扩散，使得每个白格子周围至少有一个黑格子，每个黑格子周围至少有一个白格子。在此状态下，再进行一次操作会使整个矩阵颜色相反。而由于操作次数太多了，因此大小为 $10^{6}$ 的矩阵有足够时间陷入循环。

结论3：在依据结论1的修改下，一个格子离与其最近的黑色格子（包括自己）的距离为偶数时，其最终颜色为黑色，反之为白色。

正如结论2的证明“再进行一次操作会使整个矩阵颜色相反”和“像水波一样扩散”，由于操作次数为偶数次，所以一个格子离与其最近的黑色格子（包括自己）的距离为偶数时，其最终颜色为黑色，反之为白色。

三，代码实现

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,pair<int,int>>
#define fi first
#define se second
int h,w,ans;
int xx[8]={1,0,0,-1,1,-1,1,-1};//方向数组
int yy[8]={0,-1,1,0,1,1,-1,-1};
bool safe(int x,int y){//判断该点是否在正确范围上
    return x>=1&&y>=1&&x<=h&&y<=w;
}
int main(){
    cin>>h>>w;
    vector<vector<int>>mp(h+1,vector<int>(w+1)),vis(h+1,vector<int>(w+1,0));//mp存储所在位置黑白，同时也是修改后矩阵的存储数组
    for(int i=1;i<=h;i++){//输入矩阵
        string s;
        cin>>s;
        for(int j=1;j<=w;j++){
            if(s[j-1]=='#')mp[i][j]=1;
            else mp[i][j]=0;
        }
    }
    vector<pair<int,int>>ride;//储存要依据结论1修改的格子坐标
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(mp[i][j]){
                bool is=0;
                for(int k=0;k<8;k++){
                    int ii=i+xx[k],jj=j+yy[k];
                    if(!safe(ii,jj))continue;
                    if(mp[ii][jj]==0){
                        is=1;
                        break;
                    }
                }
                if(!is)ride.push_back({i,j});
            }
        }
    }
    for(auto [x,y]:ride){
        mp[x][y]=0;//依据结论2修改点
    }
    //用优选队列保证所在格子与离其最近黑格子的距离正确，存储内容为距离、和两个坐标数
    priority_queue<PII,vector<PII>,greater<PII>>v;
     for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(mp[i][j])v.push({0,{i,j}}),vis[i][j]=1;
        }
    }
    while(v.size()){
        auto at=v.top();
        int step=at.fi,x=at.se.fi,y=at.se.se;v.pop();
        step+=1;
        mp[x][y]=step&1;//修改矩阵
        for(int i=0;i<8;i++){
            int nx=x+xx[i],ny=y+yy[i];
            if(!safe(nx,ny))continue;
            if(vis[nx][ny])continue;//确保最近
            vis[nx][ny]=1;
            v.push({step,{nx,ny}});
        }
    }
    for(int i=1;i<=h;i++){//输出矩阵
        for(int j=1;j<=w;j++){
            cout<<((mp[i][j])?("#"):("."));
        }cout<<'\n';
    }
}

本作者第二次做题解（第一次不懂规矩做的被删了），制作不易，求赞。