1 条题解

  • 0
    @ 2025-8-24 21:33:58

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Yukikaze_
    **

    搬运于2025-08-24 21:33:58，当前版本为作者最后更新于2021-05-19 10:13:06，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    简要方法：爬山+网络流

    首先，如果所有士兵不动，整个图是一个二分图，对它做最小割求出哪些位置需要拦住，然后再以士兵为左侧点、需要拦住的位置为右侧点跑费用流，即可求出一个局部最优解。

    但是这个解并不一定是最优的，因为最小割并不一定是最优解（费用流跑出来的一定是最优解），所以考虑如何求需要拦住的位置才能使得答案更优。

    注意到前面我们是默认所有士兵在的格子已经被拦住后跑的最小割，为了找出其它方案，我们选择一些士兵，然后在跑最小割时忽略这些士兵（即默认他们所在的格子是空地）。

    选士兵的方案并没有明确的最优解，因此我们用爬山来解决。

    这种方法能通过 1、2、6、7、10 号点，对于 3、4、5、9 号点，忽略所有士兵用上述方法就能通过，对于 8 号点，我们手玩一下，找出哪些空格不能选即可。

    代码基本相同：

    1、2、6、7、10：

    #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;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int 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();
//	for(i=1,cout<<'\n';i<=n;i++,cout<<'\n')
//		for(j=1;j<=m;j++) cout<<tt[i][j];
	cout<<ans<<'\n';
	for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
	return 0;
}

    3、4、5、9：

    #include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=3005,N2=65,P=3*N*N2+5,M=1e7+5,inf=1e9;
char s[N][N2],ss[N][N2],tt[N][N2];
int n,m;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
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++)
		{
			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]='.';
}
signed main()
{
	freopen("surround5.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);
	for(int t=1;t;t--)
		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));
			}
			cerr<<res<<'\n';
		}
	cout<<ans<<'\n';
	for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
	return 0;
}

    8：

    #include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=335,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;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
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]);
}
int ck(int r,int c) {return r>0&&r<=n&&c>0&&c<=m? s[r][c]=='O':0;}
bool ade()
{
	int i,j;
	memset(fst,0,sizeof(fst)),tot=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			int la=ck(i-1,j-1)+ck(i-1,j)+ck(i-1,j+1)+ck(i,j-1)+ck(i,j+1)+ck(i+1,j-1)+ck(i+1,j)+ck(i+1,j+1),
				lb=ck(i-2,j-2)+ck(i-2,j-1)+ck(i-2,j)+ck(i-2,j+1)+ck(i-2,j+2)+ck(i-1,j-2)+ck(i-1,j+2)+ck(i,j-2)+
				ck(i,j+2)+ck(i+1,j-2)+ck(i+1,j+2)+ck(i+2,j-2)+ck(i+2,j-1)+ck(i+2,j)+ck(i+2,j+1)+ck(i+2,j+2);
			add(d(i,j,0),d(i,j,1),s[i][j]!='O'&&la!=3&&lb!=5? 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]='.';
}
signed main()
{
	freopen("surround8.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);
	for(int t=1;t;t--)
		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));
			}
			cerr<<res<<'\n';
		}
	cout<<ans<<'\n';
	for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
	return 0;
}
    • 1

    [NOI2007] 调兵遣将

    信息

    ID
    2990
    时间
    3000ms
    内存
    500MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 22ms