本文主要是介绍hdu 4499 Cannon(暴力)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：hdu 4499 Cannon
题目大意：给出一个n*m的棋盘，上面已经存在了k个棋子，给出棋子的位置，然后求可以在这样的棋盘上放多少个炮，要求后放置上去的炮相互之间不能攻击。
解题思路：枚举行放的情况，用二进制数表示，每次放之前判断是否能放下（会不会和已经存在的棋子冲突），放下后判断会不会互相攻击的炮，只需要对每个新添加的炮考虑左边以及上边就可以了。
#include <cstdio>
#include <cstring>
#include <algorithm>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<<m)-1;int x, y;for (int i = 0; i < k; i++) {scanf("%d%d", &x, &y);g[x][y] = 1;}
}inline bool judgeSet(int d, int s) {for (int i = 0; i < m; i++)if ((s&(1<<i)) && g[d][i])return false;return true;
}inline void Set(int d, int s, int val) {for (int i = 0; i < m; i++)if (s&(1<<i))g[d][i] = val;
}inline bool checkup(int x, int y) {int flag = 0;for (int i = x - 1; i >= 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;
}
这篇关于hdu 4499 Cannon(暴力)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
