2200.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2200 on 2006-07-05 at 21:35:35 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 8;
const int INF = 1 << 20;
const int DIR[][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

int cnt[N][N], map[N][N], ln[N][N];
int m, n, best;
bool blk[N][N];
int debug = 0;

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
bool empty(int x, int y) { return legal(x, y) && !blk[x][y]; }
void find(int, int, int);
void posLight(int, int);
void eraseLight(int, int);

int main()
{
	int i, b;

	while(scanf("%d %d %d", &n, &m, &b) != EOF && n != 0) {
		memset(blk, false, sizeof(blk)); memset(cnt, 0, sizeof(cnt)); memset(map, -1, sizeof(map));
		memset(blk[n], true, sizeof(blk[n])); n++;
		for(i = 0; i < b; i++) {
			int x, y, bn; scanf("%d %d %d", &x, &y, &bn);
			map[x-1][y-1] = bn; blk[x-1][y-1] = true;
		}
		best = INF; find(0, 0, 0);
		if(best == INF) printf("No solution\n");
		else printf("%d\n", best);
	}
	
	return 0;
}

void find(int x, int y, int total)
{
	if(total >= best) return;
	else if(x == n) best = total;
	else if(y == m) find(x+1, 0, total);
	else {
		if(blk[x][y] && map[x][y] != -1 && map[x][y] < ln[x][y]) return;
		int i, j, en = 0;
		bool pos[2] = { true, true };
		if(blk[x][y] || cnt[x][y]) pos[1] = false;
		if(x > 0 && blk[x-1][y]) {
			if(map[x-1][y] > ln[x-1][y]+1) return;
			if(!pos[0] && map[x-1][y] == ln[x-1][y]+1) return;
		}
		for(i = 0; i < 2 && pos[0]; i++) {
			int cx = x+DIR[i+2][0], cy = y+DIR[i+2][1];
			bool end = false;
			if(!empty(cx, cy)) { end = true; en++; }
			for(j = 1; end; j++) {
				cx = x+DIR[i][0]*j; cy = y+DIR[i][1]*j;
				if(!empty(cx, cy)) break;
				else if(!cnt[cx][cy] && (i == 0 || !legal(cx+1, cy) || blk[cx+1][cy])) { pos[0] = false; break; }
			}
		}
		if(en == 2 && !blk[x][y] && !cnt[x][y]) pos[0] = false;
		for(i = 0; i < 2; i++) {
			if(!pos[i]) continue;
			bool can = true;
			if(i) posLight(x, y);
			for(j = 0; j < 4; j++) {
				int cx = x+DIR[j][0], cy = y+DIR[j][1];
				if(!legal(cx, cy)) continue;
				if(map[cx][cy] != -1 && map[cx][cy] < ln[cx][cy]) can = false;
				if(j == 0 && map[cx][cy] != -1 && map[cx][cy] != ln[cx][cy]) can = false;
			}
			if(can) find(x, y+1, total+i);
			if(i) eraseLight(x, y);
		}
	}
}
void posLight(int x, int y)
{
	int i, j; cnt[x][y] += 10;
	for(i = 0; i < 4; i++)
		for(j = 1; true; j++) {
			int cx = x+DIR[i][0]*j, cy = y+DIR[i][1]*j;
			if(!legal(cx, cy)) break;
			cnt[cx][cy]++;
			if(j == 1) ln[cx][cy]++;
			if(blk[cx][cy]) break;
		}
}
void eraseLight(int x, int y)
{
	int i, j; cnt[x][y] -= 10;
	for(i = 0; i < 4; i++)
		for(j = 1; true; j++) {
			int cx = x+DIR[i][0]*j, cy = y+DIR[i][1]*j;
			if(!legal(cx, cy)) break;
			cnt[cx][cy]--;
			if(j == 1) ln[cx][cy]--;
			if(blk[cx][cy]) break;
		}
}