2446.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 67 行

#include <stdio.h>
#include <memory.h>

const int dx[] = { 0, 1, 0, 0, -1 };
const int dy[] = { 0, 0, 1,-1, 0 };

int n, m;

inline bool inmap( int x, int y ) {
	return 0<=x&&x<n && 0<=y&&y<m;
}

int map[32][32] = { 0 };
int sign[32][32] = { 0 }, count = 0;

bool search( int x, int y ) {
	int xx, yy, i, t;

	sign[x][y] = count;

	for( i=1; i<=4; i++ ) {
		if( inmap( xx=x+dx[i], yy=y+dy[i] ) && sign[xx][yy] < count ) {
			t = map[xx][yy];
			sign[xx][yy] = count;
			if( !t || t != -1 && search( xx+dx[t], yy+dy[t] ) ) {
				map[xx][yy] = 5-i;
				map[x][y] = i;
				return true;
			}
		}
	}
	return false;
}

int main( ) {
	int i, j, h, s[2] = {0};

	scanf( "%d%d%d", &m, &n, &h );

	while( h-- ) {
		scanf( "%d%d", &i, &j );
		map[i-1][j-1] = -1;
		s[(i+j)&1]++;
	}

	if( s[0]-(n*m&1) == s[1] ) {
		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ ) 
		{
			count++;
			if( !map[i][j] && !search( i, j ) )
				goto loop;
		}
		printf( "YES\n" );
		return 0;
	}

loop:
	printf( "NO\n" );
	return 0;
}