2208.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2208 on 2006-04-18 at 12:02:47 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int BN = 8;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
const int SN = 1 << 25;

char map[BN][BN], step[SN];

bool legal(int x, int y) { return x >= 0 && x < 5 && y >= 0 && y < 5; }
int find(int);
char at(int, int, int);
void set(int&, int, int, char);

int main()
{
	int t, T, i, j;
	
	scanf("%d\n", &T);
	for(t = 0; t < T; t++) {
		int on = 0, st = 0;
		for(i = 0; i < 5; i++) {
			gets(map[i]);
			for(j = 0; j < 5; j++)
				if(map[i][j] == 'o') { on++; st |= 1 << (i*5+j); }
		}
		printf("The best case ends with %d pegs.\n", on-find(st));
	}
	
	return 0;
}

int find(int bs)
{
	memset(step, -1, sizeof(step));
	step[bs] = 0;
	queue<int> Q;
	Q.push(bs);
	int i, j, k;
	while(true) {
		int p = Q.front(); Q.pop();
		for(i = 0; i < 5; i++)
			for(j = 0; j < 5; j++) {
				if(at(p, i, j) != 'o') continue;
				for(k = 0; k < 4; k++) {
					int x = i+DIR[k][0], y = j+DIR[k][1], nx = i+2*DIR[k][0], ny = j+2*DIR[k][1];
					if(!legal(x, y) || !legal(nx, ny)) continue;
					if(at(p, x, y) != 'o' || at(p, nx, ny) != '.') continue;
					int st = p;
					set(st, x, y, '.'); set(st, i, j, '.'); set(st, nx, ny, 'o');
					if(step[st] == -1) { Q.push(st); step[st] = step[p]+1; }
				}
			}
		if(Q.empty()) return step[p];
	}
}
char at(int st, int x, int y)
{
	if(map[x][y] == '#') return '#';
	else if(st & (1<<(x*5+y))) return 'o';
	else return '.';
}
void set(int& st, int x, int y, char c)
{
	int k = (c == 'o') ? 1 : 0, p = x*5+y;
	if(k == 1) st |= 1 << p;
	else st &= ~(1<<p);
}