1 #include 2 using namespace std;
3 const int N=25;
4 const int inf=0x3f3f3f3f;
5 int n,m,d,id[N][N],edge[N*N*2][N*N*2],cnt,s,e,deth[N*N*2];
6 char w[N][N],w2[N][N];
7 int dis(int x1,int y1,int x2,int y2){
8 return abs(x1-x2)+abs(y1-y2);
9 }
10 bool bfs(){
11 memset(deth,0,sizeof(deth));
12 deth[s]=1;
13 queueint> Q;
14 Q.push(s);
15 while(!Q.empty()){
16 int cur=Q.front(); Q.pop();
17 if(cur==e) return true;
18 for(int i=0;i)
19 {
20 if(deth[i] || !edge[cur][i]) continue;
21 deth[i]=deth[cur]+1;
22 Q.push(i);
23 }
24 }
25 return false;
26 }
27 int dfs(int cur,int p){
28 if(cur==e) return p;
29 int res=0;
30 for(int i=0;i){
31 if(deth[i]!=deth[cur]+1 || !edge[cur][i]) continue;
32 int f=dfs(i,min(p-res,edge[cur][i]));
33 edge[cur][i]-=f;
34 edge[i][cur]+=f;
35 res+=f;
36 if(res==p) return res;
37 }
38 return res;
39 }
40 int Dinic(){
41 int ans=0;
42 while(bfs()) ans+=dfs(s,inf);
43 return ans;
44 }
45 int main(){
46 int cas; scanf("%d",&cas);
47 for(int T=1;T){
48 int res=0;
49 memset(edge,0,sizeof(edge)); cnt=0;
50 scanf("%d%d",&n,&d);
51 for(int i=1;i"%s",w[i]+1);
52 for(int i=1;i"%s",w2[i]+1);
53 m=strlen(w[1]+1);
54 for(int i=1;i){
55 for(int j=1;jcnt;
56 }
57 s=0;e=2*n*m+1;
58 for(int i=1;i){
59 for(int j=1;j){
60 if(w2[i][j]==‘L‘) edge[s][id[i][j]]+=1,res++;
61 if(w[i][j]>‘0‘ && (i-d1 || j-d1 || i+d>n || j+d>m)) edge[id[i][j]+n*m][e]+=inf;
62 if(w[i][j]!=‘0‘){
63 int c=w[i][j]-‘0‘;
64 edge[id[i][j]][id[i][j]+n*m]+=c;
65 for(int u=1;u){
66 for(int v=1;v){
67 if(dis(i,j,u,v)‘0‘ && (i!=u || j!=v))
68 edge[id[i][j]+n*m][id[u][v]]+=inf;
69 }
70 }
71 }
72 }
73 }
74 int ans=res-Dinic();
75 if(!ans) printf("Case #%d: no lizard was left behind.\n",T);
76 else printf("Case #%d: %d %s %s left behind.\n",T,ans,ans==1? "lizard":"lizards",ans==1? "was":"were");
77 }
78 return 0;
79 }
