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