2182.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2182 on 2006-08-26 at 20:30:53 */ 
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

const int RAND_N = 20000;
const int N = 16, K = 4;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

class Box {
private:
	int k, w, h, d[K][K], field[N][N];
	bool posIt(int, int);
	bool inBox(int x, int y) const { return x >= 0 && x < h && y >= 0 && y < w; }
	bool legal(int, int, int) const;
public:
	bool make();
	void posDomino();
};
bool Box::make() {
	scanf("%d %d %d", &k, &w, &h);
	memset(field, -1, sizeof(field));
	return k > 0;
}
bool Box::legal(int x, int y, int v) const {
	if(!inBox(x, y) || field[x][y] != -1) return false;
	else {
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(inBox(cx, cy) && field[cx][cy] != -1 && field[cx][cy] != v) return false;
		}
		return true;
	}
}
bool Box::posIt(int x, int y) {
	if(x > k) return true;
	else if(y > k) return posIt(x+1, x+1);
	else {
		for(int i = 0; i < h; i++)
			for(int j = 0; j < w; j++) {
				if(!legal(i, j, x)) continue;
				for(int k = 0; k < 4; k++) {
					int cx = i+DIR[k][0], cy = j+DIR[k][1];
					if(!legal(cx, cy, y)) continue;
					d[x][y] = (i<<12)|(j<<8)|(cx<<4)|cy;
					assert(abs(i-cx)+abs(j-cy) == 1);
					field[i][j] = x; field[cx][cy] = y;
					if(posIt(x, y+1)) return true;
					field[i][j] = field[cx][cy] = -1;
				}
			}
		return false;
	}
}
void Box::posDomino() {
	printf("%d %d %d\n", k, w, h);
	if(!posIt(0, 0)) { printf("No packing is possible\n"); return; }
	for(int i = 0; i <= k; i++)
		for(int j = i; j <= k; j++)
			printf("%d %d %d %d %d %d\n", i, j, 
				(d[i][j]>>8)&15, (d[i][j]>>12)&15, d[i][j]&15, (d[i][j]>>4)&15);
}

int main()
{
	Box box;

	while(box.make()) box.posDomino();
	
	return 0;
}