题目
题目链接:https://codeforces.com/contest/1567/problem/F
一张 \(n\times m\) 的网格,网格上有 .
和 X
。保证所有 X
都不与网格边缘相邻。给 .
赋值为 \(1\) 或 \(4\),X
赋值为 \(0,5\) 或 \(10\),求任意一种方案,使得每一个 X
的权值都等于它相邻的 .
权值之和。
\(n,m\leq 500\)。
思路
很显然只有当 X
四周有偶数个 .
才有解。
如果 X
周围只有两个 .
,那么直接把这两个 .
连边,然后黑白染色即可。
如果 X
周围有四个 .
,猜了一个结论:存在一个上下两个 .
权值相同,左右两个 .
权值相同的解。
手玩了一下感性理解的。我也不知道怎么证((。官方题解没看。
时间复杂度 \(O(nm)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=510,M=1000010;
const int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
int n,m,tot,a[N][N],b[M],head[M],pos[3];
bool flag;
char ch;
struct edge
{
int next,to;
}e[M];
int ID(int x,int y)
{
return (x-1)*m+y;
}
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot;
swap(from,to);
e[++tot]=(edge){head[from],to};
head[from]=tot;
}
void dfs(int x,int val)
{
b[x]=val;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!b[v]) dfs(v,5-val);
if (b[x]==b[v]) flag=1;
if (flag) return;
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
while (ch=getchar())
if (ch==‘.‘ || ch==‘X‘) break;
if (ch==‘X‘) a[i][j]=1;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j])
{
int sum=4;
for (int k=1;k<=4;k++)
sum-=a[i+dx[k]][j+dy[k]];
if (sum&1) return printf("NO"),0;
if (sum==2)
{
int tp=0;
for (int k=1;k<=4;k++)
if (!a[i+dx[k]][j+dy[k]]) pos[++tp]=ID(i+dx[k],j+dy[k]);
add(pos[1],pos[2]);
}
if (sum==4)
{
add(ID(i-1,j),ID(i,j-1)); add(ID(i-1,j),ID(i,j+1));
add(ID(i+1,j),ID(i,j-1)); add(ID(i+1,j),ID(i,j+1));
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!a[i][j] && !b[ID(i,j)]) dfs(ID(i,j),1);
if (flag) return printf("NO"),0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j])
for (int k=1;k<=4;k++)
{
int x=i+dx[k],y=j+dy[k];
if (!a[x][y]) b[ID(i,j)]+=b[ID(x,y)];
}
cout<<"YES\n";
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
cout<<b[ID(i,j)]<<" ";
cout<<"\n";
}
return 0;
}