在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃 到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石 柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不 变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个 石柱上。
输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱 ，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。
输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。
100%的数据满足：1<=r, c<=20, 1<=d<=4
一道很水的题目，数据规模小到不行
结果我瞎XX搞竟然搞了一个小时
太失败了
本来想加一些奇奇怪怪的小优化（找圆方面的）
结果发现数据小得不行，直接最暴力的上就行
诶
然后提交的时候还不停的RE
结果发现我memset的时候习惯打的小优化炸了
我本来习惯打meset(dep,-1,4*(t+5))的（t是汇点）
结果这次傻不拉唧的瞎XX一写（想着随便多memset一点的）
就+上了100
结果就RE了RE了RE了RE了
哇啊啊啊啊啊啊，有够坑的
这告诉我们什么呢
1、不要瞎XX乱搞
2、数组尽量开大一点（当然，注意不要MLE啊，这次RE了之后我就瞎XX乱开大数组，结果还MLE了一次，因为我算内存的时候是按结构体多少个算的，忘记了结构体里面有3个int3个int3个int3个int）
还有这种建图稍微有点复杂的题目
最好把insert输出一下
刚开始没输出时忘记读int是把那一整个01串都进来了
要读char
诶，太菜了太菜了
上我那傻不拉唧的代码：
#include<cstdio> #include<iostream> #include<cstring> const int N=800+100,M=5*1e6,inf=1e8,len=1e5; struct node { int to,next,v; }e[M]; int first[N],cnt=1,s,t,c,dep[N],qu[len],cur[N],bo[N]; int h[10]={-4,-3,-2,-1,0,1,2,3,4},l[10]={-4,-3,-2,-1,0,1,2,3,4}; int fa(int i,int j) { return (i-1)*c+j; } int fb(int u,int v,int i,int j) { return (u-i)*(u-i) +(v-j)*(v-j) ; } void insert(int u,int v,int q) { e[++cnt].to=v;e[cnt].next=first[u];first[u]=cnt;e[cnt].v=q; e[++cnt].to=u;e[cnt].next=first[v];first[v]=cnt;e[cnt].v=0; // printf("std::%d %d %d\n",u,v,q); } bool bfs() { int i=1,j=2; memset(dep,-1,sizeof(dep)); qu[i]=s;dep[s]=0; while(i!=j) { int r=qu[i++];if(i==len) i=0; for(int k=first[r];k;k=e[k].next) if(dep[e[k].to]==-1&&e[k].v>0) { dep[e[k].to]=dep[r]+1; qu[j++]=e[k].to;if(j==len)j=0; } } if(dep[t]==-1) return 0; return 1; } int dfs(int x,int a) { if(x==t||!a) return a; int flow=0; for(int &k=cur[x];k;k=e[k].next) if(e[k].v>0&&dep[e[k].to]==dep[x]+1) { int w=dfs(e[k].to,std::min(e[k].v,a)); a-=w;flow+=w; e[k].v-=w;e[k^1].v+=w; if(!a) break; } if(!flow) dep[x]=-1; return flow; } int main() { int r,d; scanf("%d %d %d",&r,&c,&d); char o; s=0;t=r*c*2+1;int w,ans=0; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { std::cin>>o; o-='0'; if(o) w=(i-1)*c+j,insert(2*w-1,2*w,o); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { std::cin>>o; if(o=='L') ans++,w=(i-1)*c+j,insert(s,2*w-1,1); } int fang=d*d; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { for(int p=0;p<9;p++) for(int q=0;q<9;q++) { if(!h[p]&&!l[q]) continue; int u=i+h[p],v=j+l[q]; if(fb(u,v,i,j)<=fang) { if(u>=1&&u<=r&&v>=1&&v<=c) insert(fa(i,j)*2,fa(u,v)*2-1,inf); else if(!bo[fa(i,j)])insert(fa(i,j)*2,t,inf),bo[fa(i,j)]=1; } } } while(bfs()) { for(int i=s;i<=t;i++) cur[i]=first[i]; ans-=dfs(s,inf); } printf("%d\n",ans); return 0; }
