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
题解：
网络流真是神奇！关键在构图！
点容量---拆点
无源无汇---附加源和汇
代码：（调了很长时间，结果竟然是insert写错了……）
uses math;
const inf=maxlongint;
type node=record
go,next,v:longint;
end;
var e:array[..] of node;
cnt,i,r,c,d,j,k,l,ans,tot,s,t:longint;
num:array[..,..,..] of longint;
first,h,q,cur:array[..] of longint;
a:array[..,..] of char;
ch:char;
procedure ins(u,v,w:longint);
begin
inc(cnt);
e[cnt].go:=v;e[cnt].v:=w;e[cnt].next:=first[u];first[u]:=cnt;
end;
procedure insert(u,v,w:longint);
begin
ins(u,v,w);ins(v,u,);
end;
function bfs:boolean;
var i,x,y,head,tail:longint;
begin
fillchar(h,sizeof(h),);
head:=;tail:=;q[]:=s;h[s]:=;
while head<tail do
begin
inc(head);
x:=q[head];
i:=first[x];
while i<> do
begin
y:=e[i].go;
if (h[y]=) and (e[i].v<>) then
begin
h[y]:=h[x]+;
inc(tail);
q[tail]:=y;
end;
i:=e[i].next;
end;
end;
exit(h[t]<>);
end;
function dfs(x,f:longint):longint;
var used,tmp,i,y:longint;
begin
if x=t then exit(f);
tmp:=;used:=;
i:=cur[x];
while i<> do
begin
y:=e[i].go;
if (h[y]=h[x]+) and (e[i].v<>) then
begin
tmp:=dfs(y,min(f-used,e[i].v));
dec(e[i].v,tmp);
inc(e[i xor ].v,tmp);
if e[i].v<> then cur[x]:=i;
inc(used,tmp);
if used=f then exit(f);
end;
i:=e[i].next;
end;
if used= then h[x]:=-;
exit(used);
end;
procedure dinic;
var i:longint;
begin
ans:=;
while bfs do
begin
for i:=s to t do cur[i]:=first[i];
inc(ans,dfs(s,inf));
end;
end;
procedure init;
begin
readln(r,c,d);
s:=;t:=*r*c+;cnt:=;
for i:= to r do
for j:= to c do
begin
num[i,j,]:=(i-)*c+j;
num[i,j,]:=(i-)*c+j+r*c;
end;
for i:= to r do
begin
for j:= to c do read(a[i,j]);
readln;
end;
for i:= to r do
for j:= to c do
if a[i,j]<>'' then
begin
insert(num[i,j,],num[i,j,],ord(a[i,j])-);
if (i-d<) or (i+d>r) or (j-d<) or (j+d>c) then insert(num[i,j,],t,inf)
else
begin
for k:=i-d to i+d do
for l:=j-d to j+d do
if sqr(abs(k-i))+sqr(abs(l-j))<=sqr(d) then insert(num[i,j,],num[k,l,],inf);
end;
end;
tot:=;
for i:= to r do
begin
for j:= to c do
begin
read(ch);
if ch<>'.' then
begin
inc(tot);
insert(s,num[i,j,],);
end;
end;
readln;
end;
end;
procedure main;
begin
dinic;
writeln(tot-ans);
end;
begin
init;
main;
end.