1 //其实这道题就是建图比较麻烦，其他还是可以的。但是最大的坑点就是
  2 //1、输出的时候的单复数，没有逃出来的猴子数为0、1的时候，要输出lizard和was，否则要输出lizards和were。我也是醉了
  3 //2、他那个条约最大距离是曼哈顿距离——d(i,j)=|X1-X2|+|Y1-Y2|.
  4 
  5 //建图的话。。st是图的起始点，en是图的终止点
  6 //首先要拆点，一个点要拆成两个点i->start和i->last。容量为这个点的承受人数
  7 //如果一个点可以向上、下、左、右移动直接跳出这个图，那他就成功逃生。就让这个i->last和en连一条容量INF的边
  8 //如果一个点它上面原来有猴子(地图上是‘L’)，那么就要让起点st和这一个点的i->start相连一条容量为1的边
  9 //如果一个点的曼哈顿距离小于规定距离，就要让i->last和j->start连一条容量INF(无穷大)边.还要建
 10 //j->last和i->start连一条边，因为两个点可以互相往来
 11 //
 12 //同时每建一条正向边，还需要建一条容量为0的反向边
 13 #include<stdio.h>
 14 #include<string.h>
 15 #include<iostream>
 16 #include<algorithm>
 17 #include<queue>
 18 #include<math.h>
 19 #include<stdlib.h>
 20 using namespace std;
 21 const int maxn=100000;
 22 const int INF=0x3f3f3f3f;
 23 int head[maxn],cnt,st,en,dis[maxn],cur[maxn];
 24 struct shudui
 25 {
 26     int x,y,z;
 27 }m[405];
 28 struct edge
 29 {
 30     int v,next,c,flow;
 31 } e[maxn];
 32 void add_edge(int x,int y,int z)
 33 {
 34     e[cnt].v=y;
 35     e[cnt].c=z;
 36     e[cnt].flow=0;
 37     e[cnt].next=head[x];
 38     head[x]=cnt++;
 39 }
 40 bool bfs()
 41 {
 42     memset(dis,0,sizeof(dis));
 43     dis[st]=1;
 44     queue<int>r;
 45     r.push(st);
 46     while(!r.empty())
 47     {
 48         int x=r.front();
 49         r.pop();
 50         for(int i=head[x]; i!=-1; i=e[i].next)
 51         {
 52             int v=e[i].v;
 53             if(!dis[v] && e[i].c>e[i].flow)
 54             {
 55                 dis[v]=dis[x]+1;
 56                 r.push(v);
 57             }
 58         }
 59     }
 60     return dis[en];
 61 }
 62 int dinic(int s,int limit)
 63 {
 64     if(s==en || !limit) return limit;
 65     int ans=0;
 66     for(int &i=cur[s]; i!=-1; i=e[i].next)
 67     {
 68         int v=e[i].v,feed;
 69         if(dis[v]!=dis[s]+1) continue;
 70         feed=dinic(v,min(limit,e[i].c-e[i].flow));
 71         if(feed)
 72         {
 73             e[i].flow+=feed;
 74             e[i^1].flow-=feed;
 75             limit-=feed;
 76             ans+=feed;
 77             if(limit==0) break;
 78         }
 79     }
 80     if(!ans) dis[s]=-1;
 81     return ans;
 82 }
 83 int main()
 84 {
 85 
 86     int t,p=0;
 87     char s[25][25];
 88     int w[25][25];
 89     scanf("%d",&t);
 90     while(t--)
 91     {
 92         int sum=0;
 93         memset(w,0,sizeof(w));
 94         memset(head,-1,sizeof(head));
 95         cnt=0;
 96         int n,d;
 97         scanf("%d%d",&n,&d);
 98         for(int i=1; i<=n; ++i)
 99         {
100             scanf("%s",s[i]+1);
101         }
102         int len=strlen(s[1]+1),number=0;
103         for(int i=1;i<=n;++i)
104         {
105             for(int j=1;j<=len;++j)
106             {
107                 if(s[i][j]!=‘0‘)
108                 {
109                     m[++number].x=i;
110                     m[number].y=j;
111                     m[number].z=s[i][j]-‘0‘;
112                 }
113             }
114         }
115         st=0;
116         en=2*number+1;
117         for(int i=1;i<=n;++i)
118         {
119             scanf("%s",s[i]+1);
120         }
121         for(int i=1;i<=n;++i)
122         {
123             for(int j=1;j<=len;++j)
124             {
125                 if(s[i][j]==‘L‘)
126                 {
127                     sum++;
128                     w[i][j]=1;
129                 }
130             }
131         }
132         for(int i=1;i<=number;++i)
133         {
134             add_edge(i,i+number,m[i].z);
135             add_edge(i+number,i,0);
136             int x=m[i].x;
137             int y=m[i].y;
138             if(y<=d || y>len-d || x<=d || x>n-d)
139             {
140                 add_edge(i+number,en,INF);
141                 add_edge(en,i+number,0);
142             }
143             if(w[x][y])
144             {
145                 add_edge(st,i,1);
146                 add_edge(i,st,0);
147             }
148             for(int j=i+1;j<=number;++j)
149             {
150                 int xx=m[j].x;
151                 int yy=m[j].y;
152                 int dist=abs(xx-x)+abs(yy-y);
153                 if(dist<=d)
154                 {
155                     add_edge(i+number,j,INF);  //这里还是要建双向边
156                     add_edge(j,i+number,0);
157                     add_edge(j+number,i,INF);
158                     add_edge(i,j+number,0);
159                 }
160             }
161         }
162 
163         int ans=0;
164         while(bfs())
165         {
166             for(int i=0; i<=en; i++)
167                 cur[i]=head[i];
168             ans+=dinic(st,1);
169         }
170 //        if(sum-ans!=0)
171 //        {
172 //            if(sum-ans!=1)
173 //            printf("Case #%d: %d lizards were left behind.\n",++p,sum-ans);
174 //            else printf("Case #%d: %d lizard were left behind.\n",++p,sum-ans);
175 //        }
176 //        else printf("Case #%d: no lizard was left behind.\n",++p);
177 //我原来这一部分的判断是像注释部分一样，原本我以为我已经绕过了单复数lizard(s)，没想到我还是掉坑里了
178 //后面的were和was也是要改的，我。。。。。。难受
179         int left=sum-ans;
180         if(left==0)
181             printf("Case #%d: no lizard was left behind.\n",++p);
182         else if(left==1)
183             printf("Case #%d: 1 lizard was left behind.\n",++p);
184         else printf("Case #%d: %d lizards were left behind.\n",++p,left);
185     }
186     return 0;
187 }