63pts求助
查看原帖
63pts求助
800499
suzhikz楼主2024/9/19 21:44
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){
	x=0;
	int f=1;char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	 x*=f;
}
const int N=805,inf=998244353;
int s=0,t=N-1;
int n,m,d;
int head[N],to[N*140],nex[N*140],w[N*140],cnt=1;
int ch[25][25],tot=1;
char sz[25][25],in[25][25];
void add(int u,int v,int ww){
	cnt++;
	to[cnt]=v;
	nex[cnt]=head[u];
	w[cnt]=ww;
	head[u]=cnt;
}
void work(int x,int y){
	add(ch[x][y],ch[x][y]+1,sz[x][y]-'0');
	add(ch[x][y]+1,ch[x][y],0);
	bool flag=0;
	for(int i=-d;i<=d;i++){
		for(int j=-d;j<=d;j++){
			if(i==0&&j==0)continue;
			if(abs(i)+abs(j)>d)continue;
			if(x+i<=0||x+i>n||y+i<=0||y+i>m){
				if(flag)continue;
				flag=1;
				add(ch[x][y]+1,t,inf);
				add(t,ch[x][y]+1,0);
			}
			if(sz[x+i][y+j]=='0')continue;
			add(ch[x][y]+1,ch[x+i][y+j],inf);
			add(ch[x+i][y+j],ch[x][y],0);
		}
	}
}
int noww[N],deep[N];
bool bfs(){
	queue<int>q;
	q.push(s);
	for(int i=1;i<N;i++)deep[i]=inf;
	while(!q.empty()){
		int x=q.front();q.pop();
		noww[x]=head[x];
		for(int i=head[x];i;i=nex[i]){
			int y=to[i];
			if(w[i]==0)continue;
			if(deep[y]!=inf)continue;
			deep[y]=deep[x]+1;
			q.push(y);
		}
	} 
	return deep[t]!=inf;
}
int dfs(int x,int summ){
//	cout<<x<<' '<<summ<<endl;
	if(x==t)return summ;
	int us=0,tmp;
	for(int i=noww[x];i;i=nex[i]){
		noww[x]=i;
		int y=to[i];
		if(deep[y]!=deep[x]+1)continue;
		if(w[i]==0)continue;
		tmp=dfs(y,min(summ,w[i]));
		summ-=tmp;
		us+=tmp;
		w[i]-=tmp;
		w[i^1]+=tmp;
		if(summ==0)break;
	}
	return us;
}
int main(){
	read(n);read(m);read(d);
	for(int i=1;i<=n;i++)scanf("%s",sz[i]+1);
	for(int i=1;i<=n;i++)scanf("%s",in[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ch[i][j]=tot;
			tot+=2;
		}
	}
	int summ=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(sz[i][j]!='0'){
				work(i,j);
			}
			if(in[i][j]=='L'){
				summ++;
				add(s,ch[i][j],1);
				add(ch[i][j],s,0);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<summ-ans;
	return 0;
}

2024/9/19 21:44
加载中...