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

F. One-Four Overload

The question ：
Here you are. $n\ast m$ The grid of ,$n<=500,m<=500$, Some lattices are ‘X’, Some lattices are ‘.’, The problem is to ensure that the outermost circle of the grid is ‘.’, Now we need to be in ‘.’ Filled in the grid of 1 perhaps 0,‘X’ Value on , It's up, down, left and right , In four directions ‘.’ The weight sum of the lattice of .
Ask if there is a color scheme , Make all ‘X’ The values on the grid are 5 Multiple . Some words , Output construction scheme .

Ideas ：
An obvious idea , We are in accordance with the ‘X’ The grid is in four directions ‘.’ The quantity classification of the lattice .
If 0, So give it to ’X’ Lattice assignment 0 ;
If 1 or 3, No matter how you fill in the numbers, it is impossible to achieve 5 Multiple .
If it is 2, Then only one of those two boxes can be filled 1, One to fill in 4;
If it is 4, Then you can only fill in two 1, Two 4;

consider 4 How to fill in the information of , If the color on the top is the same as the color on the left , So for the one in the upper left corner ’X’, If there are only two around him , Then you are not satisfied . On such consideration , We call a quantity 4 Lattice of , Fill in a number above and below , Fill in a number on the left and right , This ensures that the upper left 、 The lower left , The upper right 、 The sum of the four aspects at the bottom right is 5 Multiple .

Now it looks like , Still not able to handle . But we can see , For a lattice , It can only be filled in 1 or 4, And once you fill in a number , So the corresponding , The following figures are the only ones to be determined . I really want to color the graph , Use black and white to color the picture , Adjacent dots are dyed in different colors , You can simply think of , No matter what number you fill in first , It doesn't affect . So let's create a picture to dye .
（ It's very convenient to handle it like this , My first thought was to put a ‘X’ , One ‘.’ Such a connected graph is deducted , Re staining , It is easy to write in black and white , It's easy to understand ）;

Code ：

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