3194.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3194  User Id:fzk 
Memory:64K  Time:15MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

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

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

int search( int x, int y, int key ) {
	
	int xx, yy, i, sum = 1;
	
	map[x][y] = -1;

	for( i=0; i<4; i++ )
		if( in_map( xx=x+dx[i], yy=y+dy[i] ) && map[xx][yy] == key )
			sum += search( xx, yy, key );

	return sum;

}

int main( ) {
	int i, j, x, y;
	while( true ) {
		scanf( "%d", &n );
		if( n == 0 ) break;

		for( i=0; i<n; i++ )
		for( j=0; j<n; j++ )
			map[i][j] = 0;

		for( i=1; i<n; i++ )
			for( j=0; j<n; j++ ) {
				scanf( "%d%d", &x, &y );
				map[x-1][y-1] = i;
			}
		bool result = true;
		for( i=0; i<n; i++ )
		for( j=0; j<n; j++ )
			if( map[i][j] != -1 )
				if( search( i, j, map[i][j] ) != n ) {
					result = false;
					goto error;
				}

error:
		printf( "%s\n", result?"good":"wrong" );
	}
	return 0;
}