题目
题解

题解：

对于每根石柱，采取一分为二的想法，即把一个点分为两个点（可抽象为石柱底部到顶部），其连线容量限制为石柱高度。
超级源与所有有蜥蜴的点相连，容量为1。
超级汇与地图内所有能跳出的点相连，容量为INF。
对于地图内任意两个石柱，如果间距小于d，就将其中一根石柱的顶部与另一根石柱的底部相连，其连线容量为INF。
构图完成，剩下就是跑一遍最大流，然后用蜥蜴数量减去最大流就是最终结果。

标程：

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
struct node{
    int to,ne,w;
}e[500003];
int cnt=1,n,m,d,i,j,mp[21][21],mark[21][21],q[802],head[802],dep[802],ans,tot;
char s[23];
void ins(int u,int v,int w){
    e[++cnt]=(node){v,head[u],w};
    head[u]=cnt;
    e[++cnt]=(node){u,head[v],0};
    head[v]=cnt;
}
void build(){
    for (int i=d+1;i<=n-d;i++)
        for(int j=1;j<=d;j++){
            ins(mark[i][j]+400,801,inf);
            ins(mark[i][m-j+1]+400,801,inf);
        }
    for (int i=1;i<=d;i++)
        for (int j=1;j<=m;j++){
            ins(mark[i][j]+400,801,inf);
            ins(mark[n-i+1][j]+400,801,inf);
        }
    for (int i=d+1;i<=n;i++)
        for (int j=d+1;j<=m;j++)
            for (int x=i-d;x<=i+d;x++)
                for (int y=j-d;y<=j+d;y++)
                    if ((x!=i || y!=j) && mp[i][j] && mp[x][y] && (i-x)*(i-x)+(j-y)*(j-y)<=d*d) ins(mark[i][j]+400,mark[x][y],inf);
}
bool bfs(){
    memset(dep,-1,sizeof(dep));
    int h=0,t=1;
    q[1]=0;dep[0]=0;
    while (h<t){
        int u=q[++h];
        for (int i=head[u];i;i=e[i].ne){
            int v=e[i].to;
            if (dep[v]==-1 && e[i].w){
                dep[v]=dep[u]+1;
                q[++t]=v;
            }
        }
    }
    return dep[801]!=-1;
}
int dfs(int u,int f){
    if (u==801) return f;
    int used=0;
    for (int i=head[u];i;i=e[i].ne){
        int v=e[i].to;
        if (e[i].w && dep[v]==dep[u]+1){
            int w=dfs(v,min(f-used,e[i].w));
            used+=w;
            e[i].w-=w;e[i^1].w+=w;
            if (used==f) return f;
        }
    }
    if (!used) dep[u]=-1;
    return used;
}
void dinic(){
    while (bfs()) ans-=dfs(0,inf);
}
int main(){
    scanf("%d%d%d",&n,&m,&d);
    for (i=1;i<=n;i++){
        scanf("%s",s);
        for (j=1;j<=m;j++){
            mp[i][j]=s[j-1]^48,mark[i][j]=++tot;
            if (mp[i][j]) ins(mark[i][j],mark[i][j]+400,mp[i][j]);
        }
    }
    for (i=1;i<=n;i++){
        scanf("%s",s);
        for (j=1;j<=m;j++)
            if (s[j-1]=='L') ans++,ins(0,mark[i][j],1);
    }
    build();
    dinic();
    printf("%d",ans);
}