agc004c

一个不用保证边界没有颜色的做法。(但是四个角落有颜色还是不行)

只需要像图中那样，把一个贪吃蛇的形状染上色，再把读入的有颜色的格子给两个都染上色即可。

为什么是对的呢，因为这两个图形当中，任何一个空格子染上色，仍然是四连通的。

#include<bits/stdc++.h>
using namespace std;
#define uu unsigned
#define scanf abc=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define forg(i,x) for(int i=fir[x];i;i=nxt[i])
int abc;
typedef pair<int,int>pii;
typedef long long ll;
typedef uu long long ull;
typedef vector<int>VI;
inline int rd(int l,int r){return rand()%(r-l+1)+l;}

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int n,m,vs[503][503];char s[503][503],s1[503][503],s2[503][503];

int main(){
    cin>>n>>m;for(int i=1;i<=n;++i)cin>>s[i]+1;
    for(int i=0;i<=n+1;++i)vs[i][0]=vs[i][m+1]=3;for(int i=0;i<=m+1;++i)vs[0][i]=vs[n+1][i]=3;
    int x1=1,y1=1,x2=n,y2=m,ls=0;
    while(1){
        vs[x1][y1]=1,vs[x2][y2]=2;
        int k=-1;
        if(!vs[x1+dx[ls]][y1+dy[ls]])k=ls;else for(int o=0;o<4;++o)if(!vs[x1+dx[o]][y1+dy[o]])assert(k==-1),k=o;
        if(k==-1)break;
        x1+=dx[k],y1+=dy[k],x2-=dx[k],y2-=dy[k];ls=k;
    }
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)s1[i][j]=s2[i][j]='.';
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(vs[i][j]==1)s1[i][j]='#';else s2[i][j]='#';
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(s[i][j]=='#')s1[i][j]=s2[i][j]='#';
    for(int i=1;i<=n;++i)cout<<s1[i]+1<<endl;puts("");
    for(int i=1;i<=n;++i)cout<<s2[i]+1<<endl;
    return 0;
}