2032.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2032 on 2006-07-23 at 15:38:18 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int BN = 64;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
const char GRID[][3][5] = { { " * |", " * |", " * |" }, { "   |", "***|", "   |" }, { " * |", " **|", "   |" }, 
								{ " * |", "** |", "   |" }, { "   |", " **|", " * |" }, { "   |", "** |", " * |" } };

int map[BN][BN], w, h;
int st[BN][BN], sol[BN][BN], pn, len;

bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w && st[x][y] == -1 && map[x][y]; }
void prtSep();
void find(int, int, int, int);

int main()
{
	int t, T, i, j, k;
	char line[256];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d\n", &h, &w);
		int hl = 4*h+1;
		for(i = 0; i < hl; i++) {
			gets(line); int r = i / 4;
			if(i%4 != 2) continue;
			for(j = 0; j < w; j++)
				if(line[j*4+1] == ' ' && line[j*4+3] == ' ') map[r][j] = 0;
				else if(line[j*4+1] == '*' && line[j*4+3] == '*') map[r][j] = 1;
				else map[r][j] = 2;
		}
		pn = 0; len = 1 << 20; memset(st, -1, sizeof(st));
		for(i = 0; i < 2; i++) find(0, 0, 0, i*2);
		if(pn != 0)
			for(i = 0; i < hl; i++)
				if(i%4 == 0) prtSep();
				else {
					int io = i%4 - 1, r = i/4; putchar('|');
					for(j = 0; j < w; j++)
						if(sol[r][j] == -1) printf("   |");
						else for(k = 0; k < 4; k++) putchar(GRID[sol[r][j]][io][k]);
					putchar('\n');
				}
		printf("Number of solutions: %d\n", pn);
	}
	
	return 0;
}

void find(int x, int y, int l, int d)
{
	if(x == h-1 && y == w-1) {
		pn++;
		if(map[x][y] == 1) st[x][y] = d>>1;
		else if(d == 0) st[x][y] = 2;
		else st[x][y] = 5;
		if(l < len) { len = l; memcpy(sol, st, sizeof(sol)); }
	} else {
		int i;
		for(i = 0; i < 4; i++) {
			int o = i>>1, cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy)) continue;
			else if(map[x][y] == 1) {
				if((d>>1) != o) continue;
				else st[x][y] = d>>1;
			} else if((d>>1) == o) continue;
			else {
				st[x][y] = ((d&1)<<1) | (i&1);
				if((d>>1) && (d&1) == (i&1)) st[x][y] ^= 3;
				st[x][y] += 2;
			}
			find(cx, cy, l+1, i);
		}
	}
	st[x][y] = -1;
}
void prtSep()
{
	int i; putchar('+');
	for(i = 0; i < w; i++) printf("---+");
	putchar('\n');
}