题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1066

裸的最大流，拆点，按关系建图，然后跑一次maxflow就可以了。

代码：

eaf81a4c510fd9f94edfd36e272dd42a2934a4e9.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define MAXN 25
#define inf 0x7fffffff
#define MAXV 2010
 
struct graph {
        struct edge {
               int t,f;
               edge *next,*pair;
               edge () {
                       next=pair=NULL;
               }
        } *head[MAXV];
        int S,T;
        
        graph () {
               memset(head,0,sizeof(head));
        }
        
        void Add(int s,int t,int f) {
               edge *p=new(edge);
                p->t=t,p->f=f,p->next=head[s];
               head[s]=p;
        }
        void AddEdge(int s,int t,int f) {
               Add(s,t,f),Add(t,s,0);
               head[s]->pair=head[t],head[t]->pair=head[s];
        }
        
        int h[MAXV],gap[MAXV];
        edge *d[MAXV];
        
        int sap(int v,int flow) {
               if (v==T) return flow;
               int rec=0;
               for (edge *p=d[v];p;p=p->next) if (p->f&&h[v]==h[p->t]+1) {
                       int ret=sap(p->t,min(flow-rec,p->f));
                       p->f-=ret,p->pair->f+=ret,d[v]=p;
                       if ((rec+=ret)==flow) return flow;
               }
               if (!(--gap[h[v]])) h[S]=T;
               gap[++h[v]]++,d[v]=head[v];
               return rec;
        }
        
        int maxflow() {
               int flow=0;
               memset(h,0,sizeof(h)),memset(gap,0,sizeof(gap));
               gap[0]=T;
               for (int i=0;i++<T;) d[i]=head[i];
               while (h[S]<T) flow+=sap(S,inf);
               return flow;
        }
} g;
 
int node[MAXN][MAXN][2],V=0,n,m,di,sum=0;
char map[MAXN][MAXN];
 
int main() {
        scanf("%d%d%d",&n,&m,&di);
        for (int i=0;i++<n;) for (int j=0;j++<m;) {
               node[i][j][0]=++V,node[i][j][1]=++V;
        }
        g.S=++V;
        g.T=++V;
        for (int i=0;i++<n;) {
               scanf("%s",&map[i]);
               for (int j=0;j++<m;) if (map[i][j-1]!='0') {
                       g.AddEdge(node[i][j][0],node[i][j][1],map[i][j-1]-'0');
               }
        }
        for (int i=0;i++<n;) for (int j=0;j++<m;) {
               if (i<=di||j<=di||n+1-i<=di||m+1-j<=di) {
                       g.AddEdge(node[i][j][1],g.T,inf);
               }
        }
        for (int i=0;i++<n;) for (int j=0;j++<m;) if (map[i][j-1]!='0') {
               for (int I=0;I++<n;) for (int J=0;J++<m;) if (i!=I||J!=j) {
                       if (di>=sqrt((i-I)*(i-I)+(j-J)*(j-J))) g.AddEdge(node[i][j][1],node[I][J][0],inf);
               }
        }
        for (int i=0;i++<n;) {
               char s[MAXN];
               scanf("%s",&s);
               for (int j=0;j++<m;) if (s[j-1]=='L') g.AddEdge(g.S,node[i][j][0],1),sum++;
        }
        printf("%d\n",sum-g.maxflow());
        return 0;
}