首先,发现数据范围很小,结合题意认为这是一道搜索网络流题。
考虑建模。
我们把图中高度不为0的石柱看做点,如何连边呢?
首先,两个相互可以到达的石柱之间需要连容量为\(inf\)的边,因为如果石柱不消失,蜥蜴可以在这两个石柱之间条无数次。
然后建立汇点\(t\),每一个与边界距离不超过\(d\)的点都向\(t\)连一条容量为\(inf\)的边,因为任何一根可以跳出边界的石柱在不消失的情况下,都可以让无数只蜥蜴跳出。
接下来建立源点\(s\),\(s\)向每一个有蜥蜴的石柱连一条容量为1的边。这个很好理解,因为每个石柱上只有1只蜥蜴,所以这条边只能流过1的流量。
剩下的是最重要的,如何保证一个石柱只被踩它的高度次呢?
我们拆点,将一个石柱拆成两个点,一个连着所有入边,一个连着所有出边,入边点向出边点连容量为石柱高度的边。
然后这个网络的最大流就是答案。
注意要输出的是不能跳出边界的蜥蜴数量,所以我们要用蜥蜴总数减去答案输出。
code:
#include<bits/stdc++.h>
#define REV(x) ((x&1)?x+1:x-1)
using namespace std;
const int INF=1e9;
struct edge{int t,w,nxt;
}e[100010];
struct node{int x,y;
}d[810];
int n,m,dn,mp[25][25],t,r,cnt,be[810],dep[810],vis[810],tl,ans;
char tc;
queue<int>q;
void getn(int &x){x=getchar();while(!isdigit(x))x=getchar();x-='0';
}
void getc(char &x){x=getchar();while(x!='.'&&x!='L')x=getchar();
}
bool P(int xf,int yf,int xt,int yt){return (xf-xt)*(xf-xt)+(yf-yt)*(yf-yt)<=r*r;
}
void add(int x,int y,int v){e[++cnt].t=y,e[cnt].w=v,e[cnt].nxt=be[x],be[x]=cnt;
}
void Add(int x,int y,int v){add(x,y,v),add(y,x,0);
}
void Build(){for(int i=1;i<=dn;i+=2)for(int j=i+2;j<=dn;j+=2)P(d[i].x,d[i].y,d[j].x,d[j].y)?Add(i+1,j,INF),Add(j+1,i,INF),0:0;for(int i=1;i<=dn;i+=2)(min(d[i].x,n-d[i].x+1)<=r||min(d[i].y,m-d[i].y+1)<=r)?Add(i+1,dn+1,INF),0:0;
}
bool Getd(){memset(dep,0,sizeof(dep));int tt=0;q.push(0),dep[0]=1;while(!q.empty()){t=q.front(),q.pop(),tt++;for(int i=be[t];i;i=e[i].nxt)(!dep[e[i].t]&&e[i].w)?dep[e[i].t]=dep[t]+1,q.push(e[i].t),0:0;}return dep[dn+1];
}
int dfs(int x,int nf){if(x==dn+1)return nf;vis[x]=1;int tf,af=0;for(int i=be[x];nf&&i;i=e[i].nxt)(!vis[e[i].t]&&e[i].w&&dep[e[i].t]==dep[x]+1)?tf=dfs(e[i].t,min(nf,e[i].w)),e[i].w-=tf,e[REV(i)].w+=tf,nf-=tf,af+=tf:0;return vis[x]=0,af;
}
void Dinic(){while(Getd())ans+=dfs(0,INF);
}
int main(){scanf("%d%d%d",&n,&m,&r);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)getn(t),t?mp[i][j]=++dn,d[dn]=(node){i,j},Add(dn,dn+1,t),++dn:0;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)getc(tc),tc=='L'?(++tl,mp[i][j]?Add(0,mp[i][j],1),0:0):0;Build();Dinic();printf("%d",tl-ans);return 0;
}