记录

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int ans,x,dcnt,top=1,ls[100][100],dx[1000000],dy[1000000],ds[1000000],lscnt,t,n,m,s,l,r,c,d,i,j,u[1000000],v[1000000],w[1000000],first[1000000],nxt[10000000],second[1000000],sd[1000000],cnt[100000];
char f;
double a,b;
queue<int>q;
void add(int x,int y,int z)
{
	top++;
	u[top]=x;
	v[top]=y;
	w[top]=z;
	nxt[top]=first[x];
	first[x]=top;
	top++;
	u[top]=y;
	v[top]=x;
	nxt[top]=first[y];
	first[y]=top;
}
double dis(int x1,int y1,int x2,int y2)
{
	a=x2-x1;
	b=y2-y1;
	return sqrt(a*a+b*b);
}
bool lbdis(int x,int y)
{
	return min(abs(x),abs(y))<=d;
}
int dfs(int x,int maxflow)
{
	if(x==t)
	{
		ans+=maxflow;
		return maxflow;
	}
	int i,sum=0,mi;
	for(i=second[x];i!=0;i=nxt[i])
	{
		second[x]=i;
		if(w[i]!=0&&sd[v[i]]+1==sd[x])
		{
			mi=dfs(v[i],min(w[i],maxflow-sum));
			if(mi!=0)
			{
				w[i]-=mi;
				w[i^1]+=mi;
				sum+=mi;
				if(sum==maxflow)
					return sum; 
			}
		}
	}
	cnt[sd[x]]--;
	if(cnt[sd[x]]==0)
		sd[s]=n+1;
	sd[x]++;
	cnt[sd[x]]++;
	return sum;
}
int main()
{
	scanf("%d%d%d%c",&r,&c,&d,&f);
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			scanf("%c",&f);
			if(f!='0')
			{
				lscnt++;
				dx[lscnt]=i;
				dy[lscnt]=j;
				ds[lscnt]=f-'0';
				ls[i][j]=lscnt;
				dcnt++;
			}
		}
		scanf("%c",&f);
	}
	s=100000;
	t=200000;
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			scanf("%c",&f);
			if(f=='L')
			{
				add(s,ls[i][j],1);
				m++;
			}
		}
		scanf("%c",&f);
	}
	for(i=1;i<=lscnt;i++)
		add(i,i+10000,ds[i]);
	for(i=1;i<=lscnt;i++)
		for(j=1;j<=lscnt;j++)
			if(i!=j&&dis(dx[i],dy[i],dx[j],dy[j])<=d)
				add(i+10000,j,1e9);
	for(i=1;i<=lscnt;i++)
		if(lbdis(dx[i],dy[i]))
			add(i+10000,t,1e9);
	n=dcnt+2;
	memset(sd,-1,sizeof(sd));
	sd[t]=0;
	cnt[0]=1;
	q.push(t);
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=first[x];i!=0;i=nxt[i])
			if(sd[v[i]]==-1)
			{
				sd[v[i]]=sd[x]+1;
				cnt[sd[v[i]]]++;
				q.push(v[i]);
			}
	}
	while(sd[s]<n)
	{
		memcpy(second,first,sizeof(first));
		dfs(s,1e9);
	}
	printf("%d",m-ans);
	return 0;
}