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;
}