求助0分
查看原帖
求助0分
1295142
封禁用户楼主2024/4/4 16:45
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=105,N2=105,P=3*N*N2+5,M=1e7+5,inf=1e9;
char s[N][N2],ss[N][N2],tt[N][N2];
int n,m,fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1,que[P],dis[P],h,t,S=P-1,T=P-2,bk[P],vis[P],ch[N][N2],inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
bool dl[N][N2],Dl[N][N2];
void add(int lu,int lv,int lf,int lw=0)
{
u[++tot]=lu,v[tot]=lv,flow[tot]=lf,w[tot]=lw,nxt[tot]=fst[lu],fst[lu]=tot;
	u[++tot]=lv,v[tot]=lu,flow[tot]=0,w[tot]=-lw,nxt[tot]=fst[lv],fst[lv]=tot;
}
int d(int r,int c,int id) {return (r-1)*m+c+n*m*id;}
bool bfs()
{
memset(dis,0x3f,sizeof(dis)),dis[S]=0,que[h=t=1]=S;
	while(h<=t)
		for(int i=que[h++],j=fst[i];j;j=nxt[j])
			if(flow[j]&&dis[v[j]]>dis[i]+1) dis[v[j]]=dis[i]+1,que[++t]=v[j];
	return dis[T]<inf;
}
int dfs(int x,int lw,int tt=T)
{
	if(x==tt) return lw;
	int res=0,zl;
	for(int &i=cur[x];i;i=nxt[i])
		if(flow[i]&&dis[v[i]]==dis[x]+1&&(zl=dfs(v[i],min(lw,flow[i]),tt)))
		{
			lw-=zl,flow[i]-=zl,res+=zl,flow[i^1]+=zl;
			if(!lw) return res;
		}
	return res;
}
int dinic() {int res=0; while(bfs()) memcpy(cur,fst,sizeof(cur)),res+=dfs(S,inf); return res;}
void bfs(int x)
{
	bk[x]=1;
	for(int i=fst[x];i;i=nxt[i])
		if(!bk[v[i]]&&flow[i]) bfs(v[i]);
}
bool ade()
{
	int i,j;
	memset(fst,0,sizeof(fst)),tot=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(s[i][j]!='#'||dl[i][j]) add(d(i,j,0),d(i,j,1),s[i][j]!='O'? 1:inf);
			i<n&&(add(d(i,j,1),d(i+1,j,0),inf),add(d(i+1,j,1),d(i,j,0),inf),0),
			j<m&&(add(d(i,j,1),d(i,j+1,0),inf),add(d(i,j+1,1),d(i,j,0),inf),0),
			s[i][j]=='O'&&(add(S,d(i,j,0),inf),0);
		}
	for(i=1;i<=n;i++) add(d(i,1,1),T,inf),add(d(i,m,1),T,inf);
	for(i=2;i<m;i++) add(d(1,i,1),T,inf),add(d(n,i,1),T,inf);
	int R=dinic();
	if(R>=inf) return memset(fst,0,sizeof(fst)),tot=1,0;
	memset(bk,0,sizeof(bk)),bfs(S);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(bk[d(i,j,0)]&&!bk[d(i,j,1)]) ch[i][j]=1;
			else ch[i][j]=0;
	memset(fst,0,sizeof(fst)),tot=1;
	return 1;
}
int vs[N][N];
void adeg(int r,int c,int sr,int sc)
{
	vs[r][c]=d(sr,sc,0);
	if(ch[r][c]) add(d(sr,sc,0),d(r,c,1),1,abs(sr-r)+abs(sc-c));
	if(abs(r-sr)+abs(c-sc)>10) return;
	if(c<m&&vs[r][c+1]!=d(sr,sc,0)) adeg(r,c+1,sr,sc);
	if(c>1&&vs[r][c-1]!=d(sr,sc,0)) adeg(r,c-1,sr,sc);
	if(r<n&&vs[r+1][c]!=d(sr,sc,0)) adeg(r+1,c,sr,sc);
	if(r>1&&vs[r-1][c]!=d(sr,sc,0)) adeg(r-1,c,sr,sc);
}
int res,ans=inf;
bool spfa()
{
	memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)),q.push(S),dis[S]=0,inq[S]=1,a[S]=inf;
	while(!q.empty())
	{
		int x=q.front(); q.pop(),inq[x]=0;
		for(int i=fst[x];i;i=nxt[i])
			if(flow[i]&&dis[v[i]]>dis[x]+w[i])
				dis[v[i]]=dis[x]+w[i],pre[v[i]]=i,a[v[i]]=min(a[x],flow[i]),!inq[v[i]]&&(q.push(v[i]),inq[v[i]]=1);
	}
	if(dis[T]>inf) return 0;
	res+=dis[T]*a[T],pp+=a[T];
	for(int i=T;i!=S;i=u[pre[i]]) flow[pre[i]]-=a[T],flow[pre[i]^1]+=a[T];
	return 1;
}
int Cl;
struct aa
{
	int x1,y1,x2,y2;
}as[P];
stack<aa> st;
#define XX if(ss[x2][y2]=='#') while(!st.empty()) as[++Cl]=st.top(),st.pop();
void walk(int x1,int y1,int x2,int y2)
{
	if(x1==x2&&y1==y2) return;
	ss[x2][y2]='#';
	while(y2>y1) {st.push(aa{x2,y2-1,x2,y2}),y2--;XX}
	while(x2>x1) {st.push(aa{x2-1,y2,x2,y2}),x2--;XX}
	while(y2<y1) {st.push(aa{x2,y2+1,x2,y2}),y2++;XX}
	while(x2<x1) {st.push(aa{x2+1,y2,x2,y2}),x2++;XX}
	ss[x1][y1]='.';
}
void cal()
{
	int i,j,li;
	if(ade())
	{
		pp=qq=0;
		memset(vs,0,sizeof(vs));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				if(s[i][j]=='#'&&!ch[i][j]) adeg(i,j,i,j),add(S,d(i,j,0),1,0);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				if(ch[i][j]&&s[i][j]!='#') add(d(i,j,1),T,1,0),qq++;
		res=0;
		while(spfa());
		if(res<ans&&qq==pp)
		{
			ans=res,Cl=0;
			memcpy(ss,s,sizeof(ss));
			while(!st.empty()) st.pop();
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
					if(ss[i][j]=='#')
						for(li=fst[d(i,j,0)];li;li=nxt[li])
							if(!flow[li]&&v[li]!=S) walk(i,j,(v[li]-n*m-1)/m+1,(v[li]-n*m-1)%m+1);
			memcpy(tt,ss,sizeof(tt));
		}
	}
}
void gt()
{
	memset(dl,0,sizeof(dl)),cal();
	cerr<<ans<<'\n';
	for(int t=1000;t>1;t*=0.99)
	{
		memcpy(Dl,dl,sizeof(Dl));
		for(int i=1;i<=t;i++)
		{
			int la=rand()%n+1,lb=rand()%m+1;
			dl[la][lb]^=1;
		}
		int lp=ans;
		if(cal(),lp==ans) memcpy(dl,Dl,sizeof(dl));
		else cerr<<ans<<'\n';
	}
}
signed main()
{
	freopen("surround10.in","r",stdin);
	freopen("surround0.out","w",stdout);
	int i,j,li,lj;
	cin>>n>>m,srand(time(0));
	for(i=1;i<=n;i++) scanf("%s",s[i]+1);
	gt();
	cout<<ans<<endl;
	for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<endl;
}
2024/4/4 16:45
加载中...