题意：
给两个n*m大小的图，第一个图上都是数字(0-3)，每个数字代表一开时该坐标(i, j)上的柱子在第几次跳跃之后倒塌，0代表该位置上没有柱子，蜥蜴不能走没有柱子的地方；
第二个图由两种符号'L'和'.'组成，'L'代表此处有一个lizard(蜥蜴)，'.'代表没有蜥蜴。在同一时刻， 每个点上只能有一个蜥蜴给蜥蜴能跳的最大曼哈顿距离d，
跳到矩阵的之外，（注意是整个矩阵的外边）即可以逃出去，当一只蜥蜴所处的位置能在跳跃范围d内跳出去的话就一定会跳出去。
求最少有几只蜥蜴没跳出去。
思路：
拆点。每个点坐标表示为(i, j)第i行第j列，那么用i*m+j表示节点序号，那么把该节点拆成两个点，一个是跳入点i*m+j，一个是跳出点i*m+j+n*m，
跳入点和跳出点不断交替连接，直到可以一步跳出边界时，让该点的跳出点与超级汇点t = n*m*2+1相连，边权为n*m，因为最多有m个蜥蜴走这个点；
超级源点s = 0 与一开始是'L'的点相连，边权为1，因为一个点只有一只蜥蜴。
然后跑最大流，判断一开始的蜥蜴数sum和最终maxflow的关系，对应输出即可。
（注意下输出格式啊，was, were, lizard, lizards单复数）
#include <bits/stdc++.h> using namespace std; const int maxn = 20 + 5; const int maxm = 1e5 + 5; const int inf = 0x3f3f3f3f; int n, m, d, T, s, t, maxflow; int head[maxn*maxn*2], tot, dis[maxn*maxn*2]; char mp1[maxn][maxn], mp2[maxn][maxn]; int num[maxn][maxn], sum; struct edge{ int to, w, next; } ed[maxm]; inline void add( int u, int v, int w ){ ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot; ed[++tot].to = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot; } inline int Abs( int a ){ return a>=0 ? a:-a; } inline bool bfs(){ memset( dis, 0, sizeof(dis) ); queue<int> q; dis[s] = 1; q.push(s); while( !q.empty() ){ int x = q.front(); q.pop(); for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && !dis[y] ){ dis[y] = dis[x] + 1; q.push(y); if( y==t ) return 1; } } } return 0; } inline int min( int a, int b ){ return a<b ? a:b; } inline int dfs( int x, int flow ){ if( x==t ) return flow; int res = flow, k; for( int i=head[x]; i!=-1 && res; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && dis[y]==dis[x]+1 ){ k = dfs( y, min(res, ed[i].w) ); if( !k ) dis[y] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow - res; } inline void dinic(){ int flow = maxflow = 0; while( bfs() ) while( flow=dfs(s, inf) ) maxflow += flow; } int main(){ // freopen("in.txt", "r", stdin); scanf("%d", &T); for( int k=1; k<=T; k++ ){ tot = 1; sum = 0; memset( head ,-1, sizeof(head) ); scanf("%d %d", &n, &d); for( int i=1; i<=n; i++ ) scanf("%s", mp1[i]+1); m = strlen(mp1[1]+1); s = 0, t = n*m*2+1; for( int i=1; i<=n; i++ ){ scanf("%s", mp2[i]+1); for( int j=1; j<=m; j++ ){ num[i][j] = (i-1)*m+j; //计算点(i, j)对应的序号 if( mp2[i][j]=='L' ){ add( s, num[i][j], 1 ); //一开始有蜥蜴的点，让s与他们连边 sum ++; } } } for( int i=1; i<=n; i++ ) for( int j=1; j<=m; j++ ){ if( mp1[i][j]=='0' ) continue; //没有柱子，不处理 add( num[i][j], num[i][j]+n*m, mp1[i][j]-'0' ); if( n-i+1<=d || m-j+1<=d || j<=d || i<=d ) add( num[i][j]+n*m, t, n*m ); //该点可直接出去，与汇点连边 else{ for( int r=1; r<=n; r++ ) for( int c=1; c<=m; c++ ){ if( mp1[r][c]=='0' ) continue ; //没有柱子，不处理 if( r==i && c==j ) continue ; if( Abs(r-i)+Abs(c-j)<=d ) add( num[i][j]+n*m, num[r][c], n*m ); //符合跳跃距离，跳出点与跳入点连边 } } } dinic(); printf("Case #%d: ", k); if( maxflow==sum ) puts("no lizard was left behind."); else if( sum-maxflow==1 ) puts("1 lizard was left behind."); else printf("%d lizards were left behind. ", sum-maxflow); } return 0; }