题目链接：
https://www.luogu.org/problemnew/show/P2472
分析：
这道题用最大流解决。
首先构建模型。
一根柱子可以跳入和跳出，于是拆成两个点：入点和出点。
每一根柱子的入点和出点连一条流量为高度的边，来限制蜥蜴跳入的次数。
当柱子a可以调到柱子b时，就从a的出点向b的入点连边，流量inf。
S向所有有蜥蜴的柱子的入点连边，流量为1
T表示地图外一点，当一根柱子能跳到地图外时，则出点向T连流量为inf的边。
然后跑最大流即可。
这里要注意数组的范围以及拆点。
代码：
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
#define inf 0x7fffffff
using namespace std;
int s,t,ans;
int d[1005];
struct edge
{
int to,val,rev;
edge(int _to,int _val,int _rev)
{
to=_to;
val=_val;
rev=_rev;
}
};
vector<edge>e[1005];
void add(int x,int y,int w)
{
e[x].push_back(edge(y,w,e[y].size()));
e[y].push_back(edge(x,0,e[x].size()-1));
}
bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> q;
q.push(s);
d[s]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].to;
if(d[y]==-1 && e[x][i].val)
{
q.push(y);
d[y]=d[x]+1;
}
}
}
if(d[t]==-1)
return 0;
else
return 1;
}
int dfs(int x,int low)
{
if(x==t || low==0)
return low;
int totflow=0;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].to;
int rev=e[x][i].rev;
if(d[y]==d[x]+1 && e[x][i].val)
{
int a=dfs(y,min(low,e[x][i].val));
e[x][i].val-=a;
e[y][rev].val+=a;
low-=a;
totflow+=a;
if(low==0)
return totflow;
}
}
if(low!=0)
d[x]=-1;
return totflow;
}
void dinic()
{
while(bfs())
{
ans+=dfs(s,inf);
}
}
int main()
{
int n,m,c,cnt=0;
char ss;
scanf("%d%d%d",&n,&m,&c);
s=0,t=n*m*2+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ss;
if(ss>'0')
{
add((i-1)*m+j,(i-1)*m+j+n*m,ss-'0');
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ss;
if(ss=='L')
{
add(s,(i-1)*m+j,1);
cnt++;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(i+c>n||i-c<1||j+c>m||j-c<1)
{
add((i-1)*m+j+n*m,t,inf);
}
}
}
for(int x1=1;x1<=n;x1++)
{
for(int y1=1;y1<=m;y1++)
{
for(int x2=1;x2<=n;x2++)
{
for(int y2=1;y2<=m;y2++)
{
if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=c*c)
{
add((x1-1)*m+y1+n*m,(x2-1)*m+y2,inf);
}
}
}
}
}
dinic();
printf("%d",cnt-ans);
return 0;
}