2095.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2095 on 2006-05-26 at 21:38:59 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int DIR[][2] = { { 0, 0 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, 
						{ 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
const int N = 5, M = 3;
const int INF = 128;

int bn, w, h, press[N][N], lit[N][N], cnt[N][N], pos[N*N];
char pst[N][N];

bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w; }
void find(int, int, int);

int main()
{
	int t, i, j, k;
	
	for(t = 1; scanf("%d %d\n", &h, &w) != EOF && h != 0; t++) {
		for(i = 0; i < M; i++) gets(pst[i]);
		memset(cnt, 0, sizeof(cnt)); memset(lit, 0, sizeof(lit)); bn = INF;
		for(i = 0; i < h; i++)
			for(j = 0; j < w; j++)
				for(k = 0; k < 9; k++) {
					int x = i+DIR[k][0], y = j+DIR[k][1];
					if(legal(x, y)) cnt[x][y]++;
				}
		find(0, 0, 0);
		printf("Case #%d\n", t);
		if(bn == INF) printf("Impossible.\n");
		else for(i = 0; i < bn; i++) printf("%d%c", pos[i], (i == bn-1) ? '\n' : ' ');
	}
	
	return 0;
}

void find(int x, int y, int pn)
{
	int i, j;
	if(pn >= bn) return;
	else if(x == h) {
		for(bn = i = 0; i < h; i++)
			for(j = 0; j < w; j++)
				if(press[i][j]) pos[bn++] = i*w+j+1;
	} else if(y == w) find(x+1, 0, pn);
	else {
		for(i = 0; i < 9; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(legal(cx, cy)) cnt[cx][cy]--;
		}
		for(i = 1; i >= 0; i--) {
			press[x][y] = i; bool can = true;
			for(j = 0; j < 9; j++) {
				int cx = x+DIR[j][0], cy = y+DIR[j][1], px = 1+DIR[j][0], py = 1+DIR[j][1];
				if(!legal(cx, cy)) continue;
				if(press[x][y] && pst[px][py] == '*') lit[cx][cy] = 1-lit[cx][cy];
				if(!cnt[cx][cy] && !lit[cx][cy]) can = false;
			}
			if(can) find(x, y+1, pn+press[x][y]);
			for(j = 0; j < 9; j++) {
				int cx = x+DIR[j][0], cy = y+DIR[j][1], px = 1+DIR[j][0], py = 1+DIR[j][1];
				if(legal(cx, cy) && press[x][y] && pst[px][py] == '*') lit[cx][cy] = 1-lit[cx][cy];
			}
		}
		for(i = 0; i < 9; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(legal(cx, cy)) cnt[cx][cy]++;
		}
	}
}