在一个 r 行 c 列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 1，蜥蜴的跳跃距离是 d，即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为 1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。

输入第一行为三个整数 r，c，d，即地图的规模与最大跳跃距离。以下 r 行为石柱的初始状态，0 表示没有石柱，1~3 表示石柱的初始高度。以下 r 行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。

输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

思路

挺裸的网络流，需要注意的是如何处理每个点的最多经过次数，对于每个点 $i$ 将其拆为两个点$x_i,y_i$，并连一条最大经过次数的边，将这两个点看做整体即可。

建图：

• $S$ 到每个有蜥蜴的点 $x_i$ 建权值为 $1$ 的边
• 能跳出边界的点 $y_i$ 向 $T$ 建权值为 $+ \infty$ 的边
• $x_i$ 到 $y_i$ 建权值为 $i$ 的最多经过次数的边
• 每个点 $y_i$ 向一步能到达的点 $x_i$ 建权值为 $+ \infty$ 的边

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,D,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int tmp=0;
	for (int i=last[x];i;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            return tmp;
			}
		}
    }
    return 0;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,19260817,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
    return ans;
}
int main(){
    long long S=1005,T=1006;
    cin>>n>>m>>D;
    char a[50][50],b[50][50];
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		cin>>a[i][j];
    		add(i*m+j,n*m+i*m+j,a[i][j]-'0');
    		add(n*m+i*m+j,i*m+j,0);
		}
	}
	int cnt=0;
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		cin>>b[i][j];
    		if (b[i][j]=='L'){
		    	add(S,i*m+j,1);
		    	add(i*m+j,S,0);
		    	cnt++;
			}
    		if (i<=D||i>=n-D+1||j<=D||j>=m-D+1){
		    	add(n*m+i*m+j,T,19260817);
		    	add(T,n*m+i*m+j,0);
			}
		    for (int ii=1;ii<=n;ii++){
		    	for (int jj=1;jj<=m;jj++){
		    		if (i==ii&&j==jj){
		    			continue;
					}
					if ((ii-i)*(ii-i)+(jj-j)*(jj-j)>D*D){
						continue;
					}
		    		add(n*m+i*m+j,ii*m+jj,19260817);
		    		add(ii*m+jj,n*m+i*m+j,0);
				}
			}
		}
	}
    bfs(S,T);
    cout<<cnt-dinic(S,T);
}