1419.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1419 on 2006-03-01 at 14:05:34 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 16;

bool attack[MAX][MAX], er[MAX];
int bn, erase;

class Board {
private:
	char map[MAX][MAX];
	int w, h, o[MAX][MAX];
	inline bool legal(int, int) const;
public:
	void make();
	void relate() const;
};
inline bool Board::legal(int x, int y) const {
	return (x >= 0 && y >= 0 && x < h && y < w && o[x][y] != -1);
}
void Board::make() {
	int i, j;
	scanf("%d %d", &w, &h);
	memset(o, -1, sizeof(o));
	for(bn = i = 0; i < h; i++)
		for(j = 0; j < w; j++) {
			scanf("\n%c\n", &map[i][j]);
			if(map[i][j] != 'E') o[i][j] = bn++;
		}
}
void Board::relate() const {
	int i, j, s, lmt = max(w, h);
	memset(attack, false, sizeof(attack));
	for(i = 0; i < h; i++)
		for(j = 0; j < w; j++) {
			if(map[i][j] == 'E') continue;
			int co = o[i][j], b, e;
			bool single, str, dia;
			switch(map[i][j]) {
			case 'K': single = str = dia = true; break;
			case 'Q': single = false; str = dia = true; break;
			case 'R': single = dia = false; str = true; break;
			case 'B': single = str = false; dia = true; break;
			}
			if(map[i][j] != 'N') {
				if(single) b = -1, e = 1;
				else b = -lmt, e = lmt;
				for(s = b; s <= e; s++) {
					if(str && legal(i+s, j)) attack[co][o[i+s][j]] = true;
					if(str && legal(i, j+s)) attack[co][o[i][j+s]] = true;
					if(dia && legal(i+s, j+s)) attack[co][o[i+s][j+s]] = true;
					if(dia && legal(i+s, j-s)) attack[co][o[i+s][j-s]] = true;
				}
			} else {
				for(s = -2; s <= 2; s++)
					if(s != 0) {
						int cl = 3 - abs(s);
						if(legal(i+s, j+cl)) attack[co][o[i+s][j+cl]] = true;
						if(legal(i+s, j-cl)) attack[co][o[i+s][j-cl]] = true;
					}
			}
		}
}

void find(int, int);

int main()
{
	Board board;
	char info[MAX];

	while(gets(info) != NULL) {
		board.make(); board.relate();
		memset(er, false, sizeof(er)); erase = MAX;
		find(0, 0);
		printf("Minimum Number of Pieces to be removed: %d\n", erase);
		gets(info);
	}

	return 0;
}

void find(int o, int en)
{
	if(o == bn) erase = min(erase, en);
	else if(en < erase) {
		int i; bool must = false;
		for(i = 0; i < o; i++)
			if(!er[i] && (attack[o][i] || attack[i][o])) must = true;
		er[o] = true; find(o+1, en+1); er[o] = false;
		if(!must) find(o+1, en);
	}
}