pku2805.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
int v[1<<16];
char s_map[5][6];
char e_map[5][6];
char a_map[5][6];
int id_map[5][5];
int id_i[25], id_j[25];
int Q[1<<16];
int K;

void init()
{
	int i, j;
	memset(id_map, -1, sizeof(id_map));
	for (i = 0, K = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			if (a_map[i][j] == '#')
				continue;
			id_map[i][j] = K;
			id_i[K] = i;
			id_j[K] = j;
			K++;
		}
	}
}

int Insert(int x)
{
	if (v[x/32] & (1<<(x%32)))
		return 0;
	v[x/32] |= 1<<(x%32);
	return 1;
}

int map2int(char map[5][6])
{
	int i, j;
	int ans = 0;
	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			if (map[i][j] == 'o')
			{
				ans = ans | (1 << id_map[i][j]);
			}
		}
	}
	return ans;
}

void int2map(int x, char map[5][6])
{
	int k, i;
	memcpy(map, a_map, sizeof(a_map));
	for (k = 0; k < K; k++)
	{
		if (x & (1 << k))
			map[id_i[k]][id_j[k]] = 'o';
		else
			map[id_i[k]][id_j[k]] = '.';
	}
}

int Count(int x)
{
	int i, cnt;
	cnt = 0;
	for (i = 0; i < K; i++)
	{
		if (x & (1 << i))
			cnt++;
	}
	return cnt;
}

void outhead()
{
	int i;
	for (i = 0; i < 5; i++)
		printf("%s\n", s_map[i]);
}

int BFS()
{
	int x;
	int head, tail;
	int i, j, ni, nj;
	memset(v, 0, sizeof(v));
	x = map2int(a_map);
//	printf("x = %d\n", x);
	head = 0;
	tail = 1;
	Q[0] = x;
	while (head < tail)
	{
		int2map(Q[head], s_map);
//		printf("Q[%d]=%d\n", head, Q[head]);
//		outhead();
		head++;
		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < 5; j++)
			{
				if (s_map[i][j] == 'o')
				{
					if (i-2 >= 0 && s_map[i-1][j] == 'o' && s_map[i-2][j] == '.') //up
					{
						memcpy(e_map, s_map, sizeof(s_map));
						e_map[i-2][j] = 'o';
						e_map[i-1][j] = '.';
						e_map[i][j] = '.';
						x = map2int(e_map);
						if (Insert(x))
						{
							Q[tail++] = x;
						}
					}
					if (i+2 < 5 && s_map[i+1][j] == 'o' && s_map[i+2][j] == '.') //down
					{
						memcpy(e_map, s_map, sizeof(s_map));
						e_map[i+2][j] = 'o';
						e_map[i+1][j] = '.';
						e_map[i][j] = '.';
						x = map2int(e_map);
						if (Insert(x))
						{
							Q[tail++] = x;
						}
					}
					if (j-2 >= 0 && s_map[i][j-1] == 'o' && s_map[i][j-2] == '.') //left
					{
						memcpy(e_map, s_map, sizeof(s_map));
						e_map[i][j-2] = 'o';
						e_map[i][j-1] = '.';
						e_map[i][j] = '.';
						x = map2int(e_map);
						if (Insert(x))
						{
							Q[tail++] = x;
						}
					}
					if (j+2 < 5 && s_map[i][j+1] == 'o' && s_map[i][j+2] == '.') //right
					{
						memcpy(e_map, s_map, sizeof(s_map));
						e_map[i][j+2] = 'o';
						e_map[i][j+1] = '.';
						e_map[i][j] = '.';
						x = map2int(e_map);
						if (Insert(x))
						{
							Q[tail++] = x;
						}
					}
				}
			}
		}
	}
	return Count(Q[tail-1]);
}

void solve()
{
	int i;
	for (i = 0; i < 5; i++)
		scanf("%s", a_map[i]);
	init();
	printf("The best case ends with %d pegs.\n", BFS());
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}