题解：AT_abc460_d [ABC460D] Repeatedly Repainting

· · 题解

首先我们知道进行若干操作之后一定会进入一个中和状态，会在一个状态图 v_1,v_2 之间反复横跳。那我们需要解决的问题是：

  1. 在多少次操作后会进入中和状态？
  2. 状态图 v_1,v_2 是怎样的？

然后我们会发现一个很诡异的事情，如果一个点在第 i 次操作的时候变黑了，那么 i+2k 次也是黑的（当然，i+2k>0 且 k 是整数）。

所以我们定义一个“波及点”，表示这一次操作波及到了这个点，在最早变成“波及点”后它就一直是“波及点”。

会发现“波及点”在第一次波及之后就一直黑白反复横跳了（就是上面的结论），所以一开始的第二个问题就被我们解决了，第一个问题也被我们转化成了：每个点在第几次操作的时候被波及？答案是每个白点直接找离自己最近的黑点需要移动几次。

考虑以黑点为中心，扩展到附近的白点。

这里有一个漏洞，如果整张图全白，那么这个算法是无法正确运行的，因为我们的查找过程以黑点为基础。所以要先进行一次操作，然后再把极大值设为偶数，避免分类讨论。

#include<bits/stdc++.h>
using namespace std;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};
int h,w;
struct node{int x,y;};
queue<node> q;
int main()
{
    scanf("%d%d",&h,&w);
    char a[h+5][w+5],b[h+5][w+5];
    int dis[h+5][w+5];
    for(int i=1;i<=h;i++) scanf("%s",a[i]+1);
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            dis[i][j]=1e9;
            if(a[i][j]=='#')
            {
                for(int k=0;k<8;k++)
                {
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx<1||nx>h||ny<1||ny>w) continue;
                    if(a[nx][ny]=='.') b[nx][ny]='#';
                    else b[nx][ny]='.';
                }
            }
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(b[i][j]=='#')
            {
                q.push({i,j});
                dis[i][j]=0;
            }
        }
    }
    while(!q.empty())
    {
        int x=q.front().x;
        int y=q.front().y;
        q.pop();
        for(int i=0;i<8;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1||nx>h||ny<1||ny>w||dis[nx][ny]!=1e9) continue;
            dis[nx][ny]=dis[x][y]+1;
            q.push({nx,ny});
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(dis[i][j]%2==0) printf(".");
            else printf("#");
        }
        printf("\n");
    }
    return 0;
}