POJ_2711.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=800+10;
const int SIZE=25;
const int inf=1e9;

struct Edge {
	int v, cap;
	Edge *next, *op;
	Edge(){}
	Edge(int _v, int _c, Edge *_n):v(_v), cap(_c), next(_n){}
};

Edge *E[MAXN];
int level[MAXN], Q[MAXN];
char height[SIZE][SIZE];
int id[SIZE][SIZE];
int R, C, N, M, D;
int S, T, tot;

inline void addedge(int u, int v, int c) {
	E[u]=new Edge(v, c, E[u]); E[v]=new Edge(u, 0, E[v]);
	E[u]->op=E[v]; E[v]->op=E[u];
}

bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next)
			if (level[v=p->v]==-1&&p->cap>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (Edge *p=E[u]; p && ret<low; p=p->next)
		if (level[v=p->v]==level[u]+1 && p->cap>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->cap))) {
				ret+=tmp; p->cap-=tmp; p->op->cap+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

int dinic() {
	int maxflow=0, tmp;
	while (dinic_bfs()) {
		while (tmp=dinic_dfs(S, inf)) maxflow+=tmp;
	}
	return maxflow;
}

void init() {
	scanf("%d%d", &R, &D);
	S=0; T=801; memset(E, 0, sizeof(E));
	char buf[100]; int cnt=0;
	for (int i=1; i<=R; i++) {
		scanf("%s", height[i]+1);
		C=strlen(height[i]+1);
		for (int j=1; j<=C; j++) {
			id[i][j]=++cnt;
			if (i<=D || i+D>R || j<=D || j+D>C) addedge(id[i][j]+R*C, T, inf);
			if (height[i][j]!='0') addedge(id[i][j], id[i][j]+R*C, height[i][j]-'0');
		}
	}
	tot=0;
	for (int i=1; i<=R; i++) {
		scanf("%s", buf+1);
		for (int j=1; j<=C; j++) 
			if (buf[j]=='L') {
				addedge(S, id[i][j], 1);
				tot++;
			}
	}
	for (int i=1; i<=R; i++) 
		for (int j=1; j<=C; j++) {
			for (int x=1; x<=R; x++)
				for (int y=1; y<=C; y++)
					if (abs(i-x)+abs(j-y)<=D && height[i][j]!='0' && height[x][y]!='0') 
						addedge(id[i][j]+R*C, id[x][y], inf);
		}
}

int main() {
	int t; scanf("%d", &t);
	for (int cas=1; cas<=t; cas++) {
		init();
		int ret=tot-dinic();
		printf("Case #%d: ", cas);
		if (ret==0) puts("no lizard was left behind.");
		else if (ret==1) puts("1 lizard was left behind.");
		else printf("%d lizards were left behind.\n", ret);
	}
	return 0;
}