Codeforces Round #742 (Div. 2) F. One-Four Overload

F. One-Four Overload

题意：

给你 n ∗ m n*m n∗m的网格， n < = 500 , m < = 500 n<=500,m<=500 n<=500,m<=500，有些格子是‘X’，有些格子是‘.’，题目保证网格的最外围一圈都是‘.’，现在我们需要在‘.’的格子中填1或者0，‘X’上的值，是它上下左右，四个方向的‘.’的格子的权值和。

问有没有一种填色方案，使得所有‘X’格子上的值都是5的倍数。有的话，输出构造方案。

思路：

比较显然的思路，我们按照‘X’格子四个方向上‘.’格子的数量分类。

如果为0，那么直接给’X’格子赋值 0 ；

如果为1或3，不管怎么填数也不可能实现是5的倍数。

如果是2，那么那两个格子只能一个填1，一个填4；

如果是4，那么只能填两个1，两个4；

考虑4的情况怎么填比较好，如果上面的颜色和左边的颜色一样，那么对于左上角的一个’X’，如果他周围只有两个，那么就不满足了。处于这样的考虑，我们把一个数量为4的格子，上面和下面填一种数字，左面和右面填一种数字，这样就保证了左上、左下，右上、右下四个方面的和为5的倍数。

现在这样看来，还是不太能处理。但是我们可以发现，我们对于一个格子，只能填1或4，而且一旦填了一个数字，那么相应的，下面的数字就唯一确定了。很想图的染色，用黑白两种颜色去染图，相邻的点染不同的颜色，可以比较简单的想到，不管第一个填什么数字，都是不影响的。那么我们就建一张图去染色即可。

（这样处理起来很方便，我的第一个想法就是把一个 ‘X’ ,一个 ‘.’ 这样的连通图扣出来，再去染色，换成黑白染色的写法就很好写，也很好懂了）；

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,m;
vector<int>v[300050];
int d[][2]={1,0,0,1,-1,0,0,-1};
char mp[505][505];
int ans[300050]={0};
int id(int x,int y){
	return (x-1)*m+y;
}
int cnt(int x,int y){
	int res=0;
	for(int i=0;i<4;i++){
		int nx=x+d[i][0];
		int ny=y+d[i][1];
		if(mp[nx][ny]=='.')res++;
	}
	return res;
}
int f=1;
void dfs(int x,int w){
	ans[x]=w;
	for(int i=0;i<v[x].size();i++){
		if(!ans[v[x][i]])
			dfs(v[x][i],5-w);
		if(ans[v[x][i]]==ans[x])f=0;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>mp[i]+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='X'){
				int res=cnt(i,j);
				if(res==2){
					ans[id(i,j)]=5;
					int now=-1;
					for(int k=0;k<4;k++){
						int nx=i+d[k][0];
						int ny=j+d[k][1];
						if(mp[nx][ny]=='.'){
							if(now==-1)now=id(nx,ny);
							else {
								v[now].push_back(id(nx,ny));
								v[id(nx,ny)].push_back(now);
							}
						}
					}
				}else if(res==4){
					ans[id(i,j)]=10;
					v[id(i-1,j)].push_back(id(i,j-1));
					v[id(i-1,j)].push_back(id(i,j+1));
					v[id(i+1,j)].push_back(id(i,j+1));
					v[id(i+1,j)].push_back(id(i,j-1));

					v[id(i,j-1)].push_back(id(i-1,j));
					v[id(i,j+1)].push_back(id(i-1,j));
					v[id(i,j+1)].push_back(id(i+1,j));
					v[id(i,j-1)].push_back(id(i+1,j));
					
				}else if(res==0){
					ans[id(i,j)]=0;
				}else if(res%2==1){
					printf("NO\n");
					return 0;
				}
			}
		}
	}
	f=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='.'&&!ans[id(i,j)])
				dfs(id(i,j),4);
		}
	}
	if(!f)cout<<"NO"<<endl;
	else{
		cout<<"YES\n"<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)cout<<ans[id(i,j)]<<" ";
			cout<<endl;
		}
	}
	return 0;
}