3568916_ac_0ms_448k.cc

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

#include <iostream>
#include <algorithm>
#define inf 100000000

using namespace std;

int n;
char chess[5][5];
int map[50][50];
int LINK[50], b[50];
int l, r;
int idl[5][5], idr[5][5];

void input()
{
	for (int i = 0; i < n; i++)
	{
		cin >> chess[i];
	}
}

bool valid(int x, int y)
{
	return !(x < 0 || y < 0 || x >= n || y >= n || chess[x][y] == 'X');
}

void build()
{
	l = 0;
	r = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (valid(i, j))
			{
				l++;
				while (valid(i, j))
				{	
					idl[i][j] = l;
					j++;
				}
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (valid(j, i))
			{
				r++;
				while (valid(j, i))
				{
					idr[j][i] = r;
					j++;
				}
			}
		}
	}
	memset(map, 0, sizeof(map));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (chess[i][j] == '.')
			{
				map[idl[i][j]][idr[i][j]] = 1;
			}
		}
	}
}

int dfs(int v)
{
	int i;

	for (i = 1; i <= r; i++)
	{
		if (map[v][i] && !b[i])
		{
			b[i] = 1;
			if (LINK[i] == 0 || dfs(LINK[i]))
			{
				LINK[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

void match()
{
	int ans = 0;
	memset(LINK, 0, sizeof(LINK));
	for (int i = 1; i <= l; i++)
	{
		memset(b, 0, sizeof(b));
		ans += dfs(i);
	}
	printf("%d\n", ans);
}

int main()
{
	while (cin >> n && n != 0)
	{
		input();
		build();
		match();
	}
	return 0;
}