hdu 4499 Cannon(暴力)

題目鏈接：hdu 4499 Cannon

題目大意：給出一個n*m的棋盤，上面已經存在了k個棋子，給出棋子的位置，然後求可以在這樣的棋盤上放多少個炮，要求後放置上去的炮相互之間不能攻擊。

解題思路：枚舉行放的情況，用二進制數表示，每次放之前判斷是否能放下（會不會和已經存在的棋子沖突），放下後判斷會不會互相攻擊的炮，只需要對每個新添加的炮考慮左邊以及上邊就可以了。

#include 
#include 
#include 

using namespace std;
const int N = 10;
int c, si[N*5];

inline int bitCount(int x) {
	return x == 0 ? 0 : bitCount(x/2) + (x&1);
}

void mkdir() {
	c = 0;
	for (int i = 0; i < (1<<5); i++) {
		if (bitCount(i) <= 3)
			si[c++] = i;
	}
}

int n, m, k, ans, g[N][N], tp;

void init () {
	memset(g, 0, sizeof(g));
	ans = 0;
	tp = (1<= 0; i--) {
		if (flag && g[i][y] == 2)
			return true;
		else if (flag && g[i][y] == 1)
			return false;
		else if (g[i][y])
			flag = 1;
	}
	return false;
}

inline bool checklf(int x, int y) {
	int flag = 0;
	for (int i = y - 1; i >= 0; i--) {
		if (flag && g[x][i] == 2)
			return true;
		else if (flag && g[x][i] == 1) 
			return false;
		else if (g[x][i])
			flag = 1;
	}
	return false;
}

bool judgeOk(int d) {
	for (int i = 0; i < m; i++) {
		if (g[d][i] == 2) {
			if (checkup(d, i))
				return false;
			if (checklf(d, i))
				return false;
		}
	}
	return true;
}

void dfs(int d, int cnt) {

	if (ans >= (n-d)*3+cnt)
		return;

	if (d >= n) {
		ans = max(ans, cnt);
		return;
	}

	for (int i = 0; i < c; i++) {

		if (si[i] > tp)
			continue;

		if (judgeSet(d, si[i])) {
			Set(d, si[i], 2);

			if(judgeOk(d)) {
				dfs(d+1, cnt + bitCount(si[i]));
			}

			Set(d, si[i], 0);
		}
	}
}

int main () {
	mkdir();
	while (scanf("%d%d%d", &n, &m, &k) == 3) {
		init();
		dfs(0, 0);
		printf("%d\n", ans);
	}
	return 0;
}