题目要求无法逃离的最少有多少
直接做肯定不好做，我们帮题目变一个说法：最多能逃离多少
这个询问一看就是最大流
考虑如何建图：
1.将S和每一个有蜥蜴的点连一条流量为1的边（每个蜥蜴只能用1次）
2.每个点拆成两个点（一个点用来连接从其他点连来的边，另一个点用来向其他的点连边，下同），从前一个点向后一个点连一条流量为石柱高度的边（每个石柱只能踩它的高度次）
3.能互相到达的石柱之间连一条流量为inf的边
4.将每一个能跳出地图的点向T连一条流量为inf边
建图后跑一下最大流即可求出答案
#include <bits/stdc++.h>
#define N 1005
#define M 80005
#define inf (1<<30)
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Min(register int a,register int b)
{
return a<b?a:b;
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
struct node{
int to,next,v;
}e[M];
int head[N],cnt=1;
inline void add(register int u,register int v,register int val)
{
e[++cnt]=(node){v,head[u],val};
head[u]=cnt;
}
int n,s,t,maxflow=0,sum=0;
int px[N],py[N],tot=0;
int dep[N],gap[N],cur[N];
inline void bfs()
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
dep[t]=0;
++gap[dep[t]];
queue<int> q;
q.push(t);
while(!q.empty())
{
int u=q.front();
q.pop();
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dep[v]!=-1)
continue;
q.push(v);
dep[v]=dep[u]+1;
++gap[dep[v]];
}
}
}
inline int dfs(register int u,register int flow)
{
if(u==t)
{
maxflow+=flow;
return flow;
}
int used=0;
for(register int i=cur[u];i;i=e[i].next)
{
cur[u]=i;
int v=e[i].to;
if(e[i].v&&dep[v]+1==dep[u])
{
int tmp=dfs(v,Min(e[i].v,flow-used));
if(tmp)
{
e[i].v-=tmp;
e[i^1].v+=tmp;
used+=tmp;
}
if(used==flow)
return used;
}
}
--gap[dep[u]++]==0?dep[s]=n+1:++gap[dep[u]];
return used;
}
inline void ISAP()
{
maxflow=0;
bfs();
while(dep[s]<n)
{
memcpy(cur,head,sizeof(head));
dfs(s,inf);
}
}
int main()
{
int r=read(),c=read(),d=read();
n=r*c,s=0,t=(n<<1)+1;
for(register int i=1;i<=r;++i)
for(register int j=1;j<=c;++j)
{
char ch=getchar();
while(ch!='0'&&ch!='1'&&ch!='2'&&ch!='3')
ch=getchar();
ch-=48;
if(ch)
{
add(c*(i-1)+j,c*(i-1)+j+n,ch),add(c*(i-1)+j+n,c*(i-1)+j,0);
if(i<=d||i+d>r||j<=d||j+d>c)
add(c*(i-1)+j+n,t,inf),add(t,c*(i-1)+j+n,0);
px[++tot]=i,py[tot]=j;
}
}
for(register int i=1;i<=tot;++i)
for(register int j=i+1;j<=tot;++j)
if(d*d>=(px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j]))
{
add(c*(px[i]-1)+py[i]+n,c*(px[j]-1)+py[j],inf),add(c*(px[j]-1)+py[j],c*(px[i]-1)+py[i]+n,0);
add(c*(px[j]-1)+py[j]+n,c*(px[i]-1)+py[i],inf),add(c*(px[i]-1)+py[i],c*(px[j]-1)+py[j]+n,0);
}
for(register int i=1;i<=r;++i)
for(register int j=1;j<=c;++j)
{
char ch=getchar();
while(ch!='.'&&ch!='L')
ch=getchar();
if(ch=='L')
add(s,c*(i-1)+j,1),add(c*(i-1)+j,s,0),++sum;
}
ISAP();
write(sum-maxflow);
return 0;
}