3084684_ac_125ms_2928k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 10000000;
int n, d, m, sum;
char num[21][21], liz[21][21];
int id[21][21], cnt, ans;
int pos[401][2], map[810][810];

int min(int a,int b)
{
	return a < b ? a : b;
}

int bfs()
{
	int i, mark = 0;
	int f, r, p;
	int pre[810], visited[810];
	int queue[810];
	int C, F[810];

	f = r = -1;
	memset(pre,0,sizeof(pre));
	memset(visited,0,sizeof(visited));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	C = 21000000;
	while(f!=r)
	{
		++r;
		p = queue[r];
		for(i = 0; i < m; i++)
			if(map[p][i]&&!visited[i])
			{
				visited[i] = 1;
				queue[++f] = i;
				pre[i] = p;
				F[i] = map[p][i];
				if(i==m-1)
				{	
					mark = 1;
					goto m1;
				}
			}
	}
	m1:;
	if(mark)
	{
		p = m-1;
		while(pre[p]!=-1)
		{
			if(F[p]<C)
				C = F[p];
			p = pre[p];
		}
		p = m-1;
		while(pre[p]!=-1)
		{
			map[pre[p]][p] -= C;
			map[p][pre[p]] += C;
			p = pre[p];
		}
		ans += C;
	}
	return mark;
}

void createGraph()
{
	int i, j, len;

	cnt = sum = 0;
	memset(map,0,sizeof(map));
	for(i = 0; i < n; i++)
	{
		for(j = 0; liz[i][j]; j++)
		{
			if(num[i][j]!='0')
			{
				cnt++;
				id[i][j] = cnt;
				pos[cnt][0] = i;
				pos[cnt][1] = j;
				if(liz[i][j]=='L')
				{
					map[0][cnt] = 1;
				}
			}
		}
	}
	for(i = 0; i < n; i++)
	{
		for(j = 0; liz[i][j]; j++)
		{
			if(liz[i][j]=='L')
			{
				sum++;	
			}
			if(num[i][j]!='0')
			{
				map[id[i][j]][id[i][j]+cnt] = num[i][j]-'0';
			}
		}
	}
	len = strlen(liz[0]);
	m = cnt*2+2;
	for(i = 1; i <= cnt; i++)
	{
		int t;
		t = min(min(pos[i][1]+1,len-pos[i][1]),min(pos[i][0]+1,n-pos[i][0]));
		if(t <= d)
		{
			map[i+cnt][m-1] = inf;
		}
		for(j = i+1; j <= cnt; j++)
		{
			t = abs(pos[i][0]-pos[j][0])+abs(pos[i][1]-pos[j][1]);
			if(t <= d)
			{
				map[i+cnt][j] = map[j+cnt][i] = inf;
			}
		}
	}
}

int main()
{
	int cas, cc;

	cin >> cas;
	for(cc = 1; cc <= cas; cc++)
	{
		int i;
		cin >> n >> d;
		for(i = 0; i < n; i++)
		{
			scanf("%s",num[i]);
		}
		for(i = 0; i < n; i++)
		{
			scanf("%s",liz[i]);
		}
		createGraph();
		ans = 0;
		while(bfs());
		ans = sum - ans;
		printf("Case #%d: ",cc);
		if(ans!=0)
		{
			printf("%d lizard",ans);
			if(ans!=1)
			{
				printf("s were ");
			}
			else
			{
				printf(" was ");
			}
			puts("left behind.");
		}
		else
		{
			puts("no lizard was left behind.");
		}
	}
	return 0;
}