poj1038bugs.cpp

poj 1038 AC程序 第一次上载,不知道合适否

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 59049

bool f1[153][12], f2[153][12];
int pw[11] = { 1 };
int conv[MAX] = { 0 };
unsigned char b[MAX][10] = { 0 };
short int a[2][MAX];
int n, m, p, i, h = 0;

void dfs( int x, int s, int n )
{
	if ( x > m + 1 )
	{
		return;
	}
	if ( x == m + 1 )
	{
		a[p & 1][s] >?= n;
		return;
	}
	if ( f1[p][x] && b[i][x - 1] <= 1 && b[i][x + 1] <= 1 && b[i][x] <= 1 )
	{
		dfs( x + 3, s + 2 * pw[x - 1] + 2 * pw[x] + 2 * pw[x + 1], n + 1 );
	}
	if ( f2[p][x] && b[i][x] == 0 && b[i][x - 1] == 0 )
	{
		dfs( x + 2, s + 2 * pw[x - 1] + 2 * pw[x], n + 1 );
	}
	dfs( x + 1, s, n );
}

int main( void )
{
	int x, y, j, k, t, tmp;
	for ( i = 1; i < 11; ++i )
	{
		pw[i] = pw[i - 1] * 3;
	}
	for ( i = 0; i < MAX; ++i )
	{
		tmp = i; j = 0;
		while ( tmp > 0 )
		{
			k = tmp % 3;
			b[i][j] = k;
			if ( k > 0 )
				--k;
			conv[i] += k * pw[j++];
			tmp /= 3;
		}
	}
	scanf( "%d", &t );
	while ( t-- )
	{
		scanf( "%d%d%d", &n, &m, &k );
		memset( f1, 1, sizeof( f1 ) );
		memset( f2, 1, sizeof( f2 ) );
		while ( k-- )
		{
			scanf( "%d%d", &x, &y );
			for( i = 0; i < 2; i++ )
			{
				for( j = 0; j < 3; j++ )
				{
					if ( y - j >= 0 )
					{
						f1[x + i][y - j] = false;
					}
					if ( y - i >= 0 )
					{
						f2[x + j][y - i] = false;
					}
				}
			}
		}
		for ( i = 0; i < 12; ++i )
		{
			f2[2][i] = false;
		}
		for ( i = 0; i < pw[m]; ++i )
		{
			a[1][i] = -1;
		}
		for ( a[1][0] = 0, p = 2; p <= n; ++p )
		{
			for ( i = 0; i < pw[m]; ++i )
			{
				a[p & 1][i] = -1;
			}
			for ( i = 0; i < pw[m]; ++i )
			{
				if ( a[1 - p & 1][i] >= 0 )
				{
					dfs( 1, conv[i], a[1 - p & 1][i] );
				}
			}
		}
		for ( i = 0, tmp = 0; i < pw[m]; ++i )
		{
			if ( tmp < a[n & 1][i] )
			{
				tmp = a[n & 1][i];
			}
		}
		printf( "%d\n", tmp );
	}
	return 0;
}