pku2446.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 132 行

#include <stdio.h>
#include <string.h>
#define size 32
#define ssize 520

typedef struct Graph
{
	int id, next;
} Graph;

int M, N, K;
int map[size][size];
int odd, oddcnt, even, evencnt;
Graph G[ssize * 5];
int G_end;
const int Dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int match[ssize], vis[ssize];

int In(int x, int y)
{
	return x >= 0 && x < M && y >= 0 && y < N;
}

int DFS(int x)
{
	int p, t, id;
	p = G[x].next;
	while (p)
	{
		id = G[p].id;
		if (vis[id] == 0)
		{
			t = match[id];
			match[id] = x;
			vis[id] = 1;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[id] = t;
		}
		p = G[p].next;
	}
	return 0;
}

int Insert(int s, int e)
{
	int p;
	G[G_end].id = e;
	p = s;
	while (G[p].next)
	{
		p = G[p].next;
	}
	G[p].next = G_end++;
}

int Solve()
{
	int i, j, d, x, y;
	memset(map, 0, sizeof(map));
	oddcnt = 0;
	evencnt = 0;
	while (K--)
	{
		scanf("%d %d", &y, &x);
		x--;
		y--;
		map[x][y] = -2;
		(x + y) % 2 ? oddcnt++ : evencnt++;
	}
	odd = M * N / 2;
	even = M * N - odd;
	odd -= oddcnt;
	even -= evencnt;
	if (odd != even)
	{
		return 0;
	}
	oddcnt = 0;
	evencnt = 0;
	memset(G, 0, sizeof(G));
	G_end = ssize;
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (map[i][j] != -2)
			{
				map[i][j] = (i + j) % 2 ? oddcnt++ : evencnt++;
			}
		}
	}
	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			if ((i + j) % 2 == 0 && map[i][j] != -2)
			{
				for (d = 0; d < 4; d++)
				{
					x = i + Dir[d][0];
					y = j + Dir[d][1];
					if (In(x, y) && map[x][y] != -2)
					{
						Insert(map[i][j], map[x][y]);
					}
				}
			}
		}
	}
	memset(match, -1, sizeof(match));
	for (i = 0; i < odd; i++)
	{
		memset(vis, 0, sizeof(vis));
		if (!DFS(i))
			return 0;
	}
	return 1;
}

int main()
{
	while (EOF != scanf("%d %d %d", &M, &N, &K))
	{
		printf("%s\n", Solve() ? "YES" : "NO");
	}
	return 0;
}