Submission #76273568

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=1e6+5,M=2e6+5;
const int mod=998244353;
const int dx[8]={0,0,1,1,1,-1,-1,-1};
const int dy[8]={1,-1,0,-1,1,0,-1,1};
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,ans[N];
string s[N];
inline int get(int x,int y){
	return m*(x-1)+y;
} 
bool vis[N];
queue< array<int,3> >q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc=1;
	while(tc--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>s[i],s[i]=" "+s[i];
		int cnt=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cnt+=(s[i][j]=='#');
		if(cnt==n*m || !cnt){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++) cout<<'.';
				cout<<'\n';
			}
			exit(0);
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(s[i][j]=='.') continue;
				q.push({i,j,0});
				vis[get(i,j)]=1;
				ans[get(i,j)]=0;
			}
		int flag=0; 
		while(!q.empty()){
			auto tmp=q.front(); q.pop();
			int x=tmp[0],y=tmp[1],opt=tmp[2];
			int cur=opt+1;
			flag=max(flag,opt);
//			cout<<x<<' '<<y<<' '<<opt<<'\n'; 
			for(int o=0;o<8;o++){
				int nowx=x+dx[o],nowy=y+dy[o];
				if(nowx<1 || nowy<1 || nowx>n || nowy>m || vis[get(nowx,nowy)]) continue;
				vis[get(nowx,nowy)]=1;
				ans[get(nowx,nowy)]=cur;
				q.push({nowx,nowy,cur});
			}
		}
//		cout<<"----------\n"; 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(ans[get(i,j)]%2==0){
					if(flag%2==0) cout<<'#';
					else cout<<'.'; 
				}
				else{
					if(flag%2==0) cout<<'.';
					else cout<<'#';
				}
			}
			cout<<'\n';
		}
		/*for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cout<<ans[get(i,j)]<<" \n"[j==m]; */
	}
	return 0;
}
/*

*/

Submission Info

Judge Result