2458.txt

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

#include "stdio.h"
char map[6][6];
bool sign[6][6];
int flag[6][6];
bool inline inmap( int x, int y )
{
	return 0<=x&&x<5&&0<=y&&y<5;
}
int dx[]={ 0,-1, 0, 1};
int dy[]={-1, 0, 1, 0};
int ans;
int reach;
int visit;
void find( int x, int y )
{
	int i, xx, yy;
	reach++;
	flag[x][y] = visit;

	for( i=0; i<4; i++ )
	if( inmap( xx=x+dx[i], yy=y+dy[i] ) && !sign[xx][yy] && flag[xx][yy] < visit )
	{
		find( xx, yy );
		if( reach == 7 ) return;
	}
}
void search( int j , int step , int J, int H )
{
	int i = j;
	if( H >= 4 )return;
	if( step == 7 )
	{
		reach = 0;
		visit++;
		find( i/5, i%5 );
		if( reach == 7 ) ans++;		
		return;
	}
	for( i++; i<25 &&( j<0 || ( i/5 - j/5 ) <= 1 ); i++ )
	{
		sign[i/5][i%5] = false;
		search( i, step+1, J+(int)(map[i/5][i%5]=='J'), H+(int)(map[i/5][i%5]=='H') );
		sign[i/5][i%5] = true;
	}
}
int main()
{
	int i, j;
	for( i=0; i<5; i++ )	
		scanf( "%s", map[i] );	
	for( i=0; i<5; i++ )
	for( j=0; j<5; j++ )
	{
		sign[i][j] = true;
		flag[i][j] = 0;
	}
	ans = 0;visit = 0;	
	search( -1, 0, 0, 0 );
	printf( "%d\n", ans );
	return 0;
}