全国大学生算法设计与编程挑战赛 （秋季赛）——正式赛

染方块-color

Description

现在有一个 n \times nn×n 的方格，每一个格子是红块（X），绿块 (O)，或者空白块 (.) ，而你可以把空白块染成红色。

在你对你想染色的空白块进行染色之后，方格会有这样的变化：如果一个绿色块上下左右都是红块，这个绿块就会变成空白块。

给定方格的初始状态，你现在可以对其进行符合条件的染色，求空格最大能达到多少个。

为了方便处理，我们保证没有任意两个绿块边相邻，任意一个绿块上下左右必定有一个空白块,同时假定棋盘边界外的部分全都是红块。

Input

nn 行字符串，每行字符串有 nn 个字符,从左上到右下表示这个棋盘的状态。

Output

一行一个整数 ansans ， 表示经过染色后最多能有多少个空格。

Sample Input 1 

.XOX.
.O.OX
X.O.O
OX.OX
.OX..

Sample Output 1

12

Hint

样例解释：

.X.X.
.OX.X
X.OX.
.X.OX
X.X..

​数据范围

n \leq 50n≤50

代码

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5+5;
const int inf = 0x7fffffff;

struct nd{
	int ne,to,w;
}e[N<<1];

int n,m,S,T,ans,cnt=1,head[N],d[N];

void in(int x,int y,int w){
	e[++cnt].to=y;e[cnt].w=w;e[cnt].ne=head[x];head[x]=cnt;
	e[++cnt].to=x;e[cnt].w=0;e[cnt].ne=head[y];head[y]=cnt;
}

bool bfs(){
	queue<int>q;
	for(int i=1;i<=n/*T*/;++i)d[i]=0;
	q.push(S);d[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].ne){
			int y=e[i].to;
			if(!d[y]&&e[i].w>0){
				d[y]=d[x]+1;
				q.push(y); 
			}
		}
	}
	return d[T]!=0;
}

int dinic(int x,int mn){
	if(x==T||!mn)return mn;
	int flow=0;
	for(int i=head[x];i;i=e[i].ne){
		int y=e[i].to,tmpf;
		if(d[y]==d[x]+1&&(tmpf=dinic(y,min(e[i].w,mn)))>0){
			e[i].w-=tmpf;e[i^1].w+=tmpf;
			mn-=tmpf;flow+=tmpf;
			if(!mn)break;
		}
	}
	if(!flow)d[x]=0;
	return flow;
}

char s[55][55];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,-1,1};
int p[55][55];

int main(){
	int a=1,tot=0;
	for(int i=1;i<=a;++i){
		scanf("%s",s[i]+1);
		if(i==1)a=strlen(s[i]+1);
	}
	for(int i=1;i<=a;++i)
	for(int j=1;j<=a;++j)
	if(s[i][j]=='O'){
		++tot;
		p[i][j]=tot;
	}
	else if(s[i][j]=='.'){
		++tot;
		p[i][j]=tot;
	}
	S=tot+1;T=tot+2; 
	n=T;
	int ans=tot;
	for(int i=1;i<=a;++i)
	for(int j=1;j<=a;++j)
	if(s[i][j]=='O'){
		for(int k=0;k<4;++k){
			int x=i+fx[k],y=j+fy[k];
			if(x<1||x>a||y<1||y>a)continue;
			if(s[x][y]=='.'){
				in(p[i][j],p[x][y],inf);
			}
		}
		in(S,p[i][j],1);
	}
	else if(s[i][j]=='.'){
		in(p[i][j],T,1);
	}
	while(bfs())ans-=dinic(S,inf);
	printf("%d\n",ans);
}