传送门
题意:
给你一个
n
?
m
n*m
n?m的矩形,包含
.
.
.和
X
X
X,你有两种颜色,你需要给
.
.
.染色使得每个
X
X
X上下左右相邻的
.
.
.其两种颜色个数相同,输出一种合法方案。
1
≤
n
,
m
≤
500
1\le n,m\le 500
1≤n,m≤500
思路:
考虑
X
X
X周围
.
.
.的个数的情况。
(
1
)
(1)
(1) 当有奇数个
.
.
.的时候,显然不可能有合法解。
(
2
)
(2)
(2)当有两个
.
.
.的时候,我们将其连边,变成一个图,显然可以直接二分图染色构造答案。
(
3
)
(3)
(3)当有四个
.
.
.的时候,这个就比较麻烦了,一种可行方案就是
(
x
?
1
,
y
)
<
=
>
(
x
,
y
?
1
)
(x-1,y)<=>(x,y-1)
(x?1,y)<=>(x,y?1)连边,
(
x
+
1
,
y
)
<
=
>
(
x
,
y
+
1
)
(x+1,y)<=>(x,y+1)
(x+1,y)<=>(x,y+1)连边,让后跑二分图染色即可。
对于
(
3
)
(3)
(3)的正确性官方题解有说,其实并没怎么看懂,但是自己画一下应该可以发现这样是可以的,因为要是出来奇数环的话需要奇数条边,而这种斜边必须是偶数个,那么横边必须是奇数个,貌似可以感性认知一下?雀氏不是很会证。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N=510,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;
int n,m;
PII a[N];
char s[N][N];
int dir[4][2]={-1,0,0,-1,1,0,0,1};
vector<int>v[N*N*2];
int col[N*N],flag;
int id(int x,int y) {
return (x-1)*m+y;
}
void dfs(int u,int color) {
if(flag) return;
col[u]=color;
for(auto x:v[u]) {
if(flag) break;
if(!col[x]) dfs(x,3-color);
else if(col[x]==color) flag=1;
}
}
bool check() {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]!='X') continue;
int cnt=0;
for(int k=0;k<4;k++) {
int dx=i+dir[k][0];
int dy=j+dir[k][1];
if(dx<1||dy<1||dx>n||dy>m) continue;
cnt+=s[dx][dy]=='.';
if(s[dx][dy]=='.') a[cnt]={dx,dy};
}
if(cnt%2) return false;
if(cnt==2) {
v[id(a[1].X,a[1].Y)].pb(id(a[2].X,a[2].Y));
v[id(a[2].X,a[2].Y)].pb(id(a[1].X,a[1].Y));
} else {
v[id(a[1].X,a[1].Y)].pb(id(a[2].X,a[2].Y));
v[id(a[2].X,a[2].Y)].pb(id(a[1].X,a[1].Y));
v[id(a[3].X,a[3].Y)].pb(id(a[4].X,a[4].Y));
v[id(a[4].X,a[4].Y)].pb(id(a[3].X,a[3].Y));
}
}
}
flag=0;
for(int i=1;i<=n*m;i++) col[i]=0;
for(int i=1;i<=n*m;i++) if(s[(i-1)/m+1][(i-1)%m+1]!='X'&&!col[i]&&!flag) dfs(i,1);
if(flag) return false;
puts("YES");
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
int val=id(i,j);
if(s[i][j]=='X') {
int cnt=0;
for(int k=0;k<4;k++) {
int dx=i+dir[k][0];
int dy=j+dir[k][1];
if(dx<1||dy<1||dx>n||dy>m) continue;
cnt+=s[dx][dy]=='.';
if(s[dx][dy]=='.') a[cnt]={dx,dy};
}
if(cnt==0) printf("0 ");
else if(cnt==2) printf("5 ");
else printf("10 ");
}
else if(col[val]==1) printf("1 ");
else printf("4 ");
}
puts("");
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
if(!check()) puts("NO");
int x;
return 0;
}
|