Description
在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。
Input
输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。
Output
输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。
Sample Input
5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
Sample Output
1
HINT
100%的数据满足：1<=r, c<=20, 1<=d<=3
拆点网络流。一个点拆成左右两个，能离开的点右边向T连一条容量无限的边，有蜥蜴的点S向左边的点连一条容量为1的边，如果点上有石柱，左边的点向右边的点连一条容量为石柱高度的边。最后可互相到达的点右边向左边连一条容量无限的边。最后跑一遍最大流，答案是蜥蜴数-最大流ans。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
#define S 0
#define T 80001
#define inf 2<<28
struct edge{
int to,v,next;
}e[500001];
int r,c,d,ans,cnt=1;
int h[400000],head[400000];
int q[400000];
int mark[201][201];
bool escape(int x,int y)
{
if (x<=d||y<=d||x>r-d||y>c-d) return 1;
return 0;
}
int num(int x,int y)
{
return (x-1)*c+y;
}
bool dist(int x1,int y1,int x2,int y2)
{
int x=x1-x2;
int y=y1-y2;
return x*x+y*y<=d*d;
}
void ins(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void insert(int u,int v,int w)
{
ins(u,v,w);
ins(v,u,0);
}
bool bfs()
{
memset(h,-1,sizeof(h));
int t=0,w=1,i,now;q[0]=h[0]=0;
while(t<w)
{
now=q[t];t++;i=head[now];
while(i)
{
if(e[i].v&&h[e[i].to]==-1)
{
h[e[i].to]=h[now]+1;
q[w++]=e[i].to;
}
i=e[i].next;
}
}
if(h[T]==-1)return 0;return 1;
}
int dfs(int x,int f)
{
if(x==T)return f;
int i=head[x],used=0,w;
while(i)
{
if(e[i].v&&h[e[i].to]==h[x]+1)
{
w=f-used;w=dfs(e[i].to,min(w,e[i].v));
e[i].v-=w;e[i^1].v+=w;
used+=w;if(used==f)return f;
}
i=e[i].next;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans-=dfs(0,inf);}
void init()
{
cin>>r>>c>>d;
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
{
char ch;
cin>>ch;
if (escape(i,j))
insert(c*r+num(i,j),T,inf);
if (ch=='0') continue;
mark[i][j]=(int)(ch-'0');
}
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
{
char ch;
cin>>ch;
if (ch=='L')
{
insert(S,num(i,j),1);
ans++;
}
}
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
{
if (mark[i][j])
insert(num(i,j),c*r+num(i,j),mark[i][j]);
if (mark[i][j])
for (int k=1;k<=r;k++)
for (int l=1;l<=c;l++)
{
if (!mark[k][l]||k==i&&j==l) continue;
if (!dist(i,j,k,l)) continue;
insert(c*r+num(i,j),num(k,l),inf);
}
}
}
int main()
{
init();
dinic();
cout<<ans;
}