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 }