HDU - 5113 Black And White 搜索+剪枝 （ 2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交））

直接 dfs 爆搜， 从第一个位置开始选填颜色

但是要加一个剪枝，防止超时：剩余的每个颜色的数目  都要小于等于  没填色颜色的的格子数的一半 （奇数的时候要加一）

这份代码写的比较急，很丑 ，待优化

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <algorithm>
#include <sstream>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
using namespace std;
typedef long long ll;
const int maxn =
7, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int T, n, m, k;
int mp[maxn][maxn];
int a[maxn*maxn], vis[maxn][maxn];
int dx[5] = {1, 0, -1, 0};
int dy[5] = {0, 1, 0, -1};
void init() {
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= k; ++i)
scanf("%d", &a[i]);
memset(mp, 0, sizeof mp);
}
bool dfs(int x, int y, int cnt) {
if(cnt == n*m) return true;
for(int ii = 0; ii < 4; ++ii) {
int xx = x + dx[ii], yy = y + dy[ii];
if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
if(vis[xx][yy]) continue;
vis[xx][yy] = 1;
int f = 0;
for(int i = 1; i <= k; ++i) {
if(a[i]) {
int j;
for(j = 0; j < 4; ++j) {
int nx = xx + dx[j], ny = yy + dy[j];
if(mp[nx][ny] == i) break;
}
if(j == 4) {
f = 1;
a[i]--;
mp[xx][yy] = i;
int t = (n*m-cnt)/2, f_ = 1;
for(int i = 1; i <= k; ++i)
if(a[i] > t) { f_ = 0; break; }
if(f_ && dfs(xx, yy, cnt+1)) return true;
a[i]++;
mp[xx][yy] = 0;
}
}
}
if(f == 0) { vis[xx][yy] = 0; return false; }
vis[xx][yy] = 0;
}
return false;
}
void solve() {
for(int i = 1; i <= k; ++i) {
a[i]--;
memset(vis, 0, sizeof vis);
vis[1][1] = 1;
mp[1][1] = i;
if(dfs(1, 1, 1)) {
puts("YES");
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
printf("%d%c", mp[i][j], (j == m ? 'n' : ' '));
}
//cout << "++++++++++++++++++++++++2333" << endl;
return;
}
a[i]++;
vis[1][1] = 0;
mp[1][1] = 0;
}
puts("NO");
}
int main() {
scanf("%d", &T);
int kase = 1;
while(T--) {
init();
printf("Case #%d:n", kase++);
solve();
}
return 0;
}

最后

以上就是纯真康乃馨为你收集整理的HDU - 5113 Black And White 搜索+剪枝 （ 2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交））的全部内容，希望文章能够帮你解决HDU - 5113 Black And White 搜索+剪枝 （ 2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交））所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。