描述 Description
在一个 r 行 c 列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为 1，蜥蜴的跳跃距离是 d，即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为 1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。
输入格式 InputFormat
输入第一行为三个整数 r，c，d，即地图的规模与最大跳跃距离。以下 r 行为石竹的初始状态，0 表示没有石柱，1~3 表示石柱的初始高度。以下 r 行为蜥蜴位置，“L” 表示蜥蜴，“.” 表示没有蜥蜴。
输出格式 OutputFormat
输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。
样例输入 SampleInput
11 8 1
11211221
31310220
02220113
23001302
00103033
33300203
33030032
20013100
30132221
33310002
32232333
.L..L.LL
.LL..LL.
..LL….
LL..LL.L
……LL
.LL..L..
.L…..L
…LL…
L.LL…L
L..L…L
.L.L….
样例输出 SampleOutput
5
石柱拆点自身连一条容量为高度的边，建立源点汇点，源点向有蜥蜴的柱子连容量为一的边，能跳出界的柱子向汇点连容量为无穷大的边。答案为总数减去最大流。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=1005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,fl,nx;
}e[maxn*maxn];
struct point
{
int x,y,h;
};
int head[maxn],dis[maxn],used[maxn],cur[maxn];
int cnt,num,c,d;
deque <int> q;
vector <point> v;
char ch;
inline bool can(int a,int b)
{
return ((double)sqrt((double)(v[a].x-v[b].x)*(v[a].x-v[b].x)+(double)(v[a].y-v[b].y)*(v[a].y-v[b].y))<=d);
}
inline void ins(int u,int v,int flow)
{
e[cnt++]=(edge){v,flow,head[u]};head[u]=cnt-1;
e[cnt++]=(edge){u,0,head[v]};head[v]=cnt-1;
}
inline bool bfs(int s,int t,int tim)
{
int i,j,u,v,w;
while (!q.empty()) q.pop_front();
dis[s]=0;used[s]=tim;
q.push_back(s);
while (!q.empty())
{
u=q.front();q.pop_front();
for (i=head[u];i!=-1;i=e[i].nx)
{
v=e[i].to;
if (used[v]!=tim && e[i].fl>0)
{
used[v]=tim;
dis[v]=dis[u]+1;
q.push_back(v);
}
}
}
return (used[t]==tim);
}
int dfs(int u,int t,int flow)
{
int i,j,v,d,k;
if (u==t) return flow;
d=flow;
for (i=cur[u];i!=-1;i=e[i].nx)
{
v=e[i].to;
if (dis[v]==dis[u]+1 && e[i].fl>0)
{
k=dfs(v,t,min(d,e[i].fl));
e[i].fl-=k;e[i^1].fl+=k;d-=k;
if (d==0) break;
}
}
return flow-d;
}
inline void dinic(int s,int t)
{
int i,ans=0;
while (bfs(s,t,++num))
{
memcpy(cur,head,sizeof(head));
ans+=dfs(s,t,inf);
}
printf("%d\n",m-ans);
}
int main()
{
cnt=num=m=0;
memset(head,-1,sizeof(head));
scanf("%d%d%d",&r,&c,&d);
v.clear();
for (i=1;i<=r;i++) for (j=1;j<=c;j++)
{
ch=getchar();while (ch<'0' || ch>'9') ch=getchar();
if (ch!='0') v.push_back((point){i,j,ch-'0'});
}
n=v.size();
for (i=0;i<n;i++)
{
ins(i+1,n+i+1,v[i].h);
for (j=0;j<n;j++) if (can(i,j)) ins(n+i+1,j+1,inf);
if (v[i].x<=d || v[i].x>r-d || v[i].y<=d || v[i].y>c-d) ins(n+i+1,2*n+1,inf);
}
k=0;
for (i=1;i<=r;i++) for (j=1;j<=c;j++)
{
ch=getchar();while (ch!='.' && ch!='L') ch=getchar();
if (ch=='L')
{
m++;
while (v[k].x!=i || v[k].y!=j) k++;
ins(0,k+1,1);
}
}
dinic(0,2*n+1);
return 0;
}