2166.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2166 on 2006-03-08 at 17:24:57 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long int64;
const char *SEP_LINE = "--------";
const int DIR[][2] = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };
const int D_MAX = 32;
const int S_MAX = 380000;
const int ELE_N = 36;
const int POS[][2] = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 0 }, { 6, 0 }, { 7, 0 }, 
						{ 7, 0 }, { 7, 1 }, { 7, 2 }, { 7, 3 }, { 7, 4 }, { 7, 5 }, { 7, 6 }, { 7, 7 }, 
						{ 7, 7 }, { 6, 7 }, { 5, 7 }, { 4, 7 }, { 3, 7 }, { 2, 7 }, { 1, 7 }, { 0, 7 }, 
						{ 0, 7 }, { 0, 6 }, { 0, 5 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, { 0, 1 }, { 0, 0 } };

class Box {
private:
	int64 hide;
	char out[D_MAX];
	bool atom(int, int) const;
	int enter(int) const;
public:
	Box();
	void set(const char*);
	int test(int);
	void show() const;
};
Box::Box() { 
	hide = 0; int i;
	for(i = 0; i < D_MAX; i++) out[i] = -10;
}
bool Box::atom(int x, int y) const {
	if(x <= 0 || y <= 0 || x >= 7 || y >= 7) return false;
	else return (hide>>(x*6+y-7))&1 != 0;
}
int Box::enter(int o) const {
	int x = POS[o][0], y = POS[o][1], dir = o>>3;
	while(true) {
		int cx = x+DIR[dir][0], cy = y+DIR[dir][1];
		if(cx < 0) return 31-cy;
		else if(cx >= 8) return 8+cy;
		else if(cy < 0) return cx;
		else if(cy >= 8) return 23-cx;
		else if(atom(cx, cy)) return -1;
		bool left = false, right = false;
		if(atom(cx+DIR[(dir-1)&3][0], cy+DIR[(dir-1)&3][1])) left = true;
		if(atom(cx+DIR[(dir+1)&3][0], cy+DIR[(dir+1)&3][1])) right = true;
		if(left && right) return o;
		else if(left) dir = (dir+1)&3;
		else if(right) dir = (dir-1)&3;
		else { x = cx; y = cy; }
	}
}
int Box::test(int o) {
	if(out[o] == -10) out[o] = (char)enter(o);
	return out[o];
}
void Box::set(const char* s) {
	int i = 0;
	for(i = 0; i < ELE_N; i++) hide |= (int64)('1'-s[i]) << i;
}
void Box::show() const {
	puts(SEP_LINE); int i, j;
	for(i = 0; i < 6; i++) {
		putchar('-');
		for(j = 0; j < 6; j++) putchar("-+"[(hide>>(i*6+j))&1]);
		printf("-\n");
	}
	puts(SEP_LINE);
}

Box box[S_MAX];

int main()
{
	int i, j, bn = 0, n, data[D_MAX][2];
	char pos[] = "000001111111111111111111111111111111";

	do box[bn++].set(pos);
	while(next_permutation(pos, pos+ELE_N));
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) scanf("%d %d", &data[i][0], &data[i][1]);
		int found = 0, fo;
		for(i = 0; i < bn && found < 2; i++) {
			bool right = true;
			for(j = 0; j < n; j++)
				if(box[i].test(data[j][0]) != data[j][1]) { right = false; break; }
			if(right) { found++; fo = i; }
		}
		if(found != 1) printf("NO\n");
		else box[fo].show();
	}
	
	return 0;
}