首页 > 代码库 > uva 646 - The Gourmet Club(暴力)
uva 646 - The Gourmet Club(暴力)
题目链接:uva 646 - The Gourmet Club
题目大意:有16个人参加聚会,聚会一共5天,每天有4桌,每桌4个人,一起吃饭的4个人会互相认识。现在要安排座位使得16个任意两个人都互相认识。给出前三天的安排,求后两天的安排。
解题思路:任意两个人之间肯定只能同桌一次。所以根据这个条件,只要枚举出第4天的第1桌的情况,就可推导出所有的,或者是矛盾。
在Poj和Zoj上都过了,uva上过不了,求大神指教。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 20;
char s[N][N];
bool flag;
int g[N][N], ans[8][4];
int c[N], can[N][N], v[N];
bool init () {
flag = false;
char str[N];
memset(g, 0, sizeof(g));
memset(c, 0, sizeof(c));
for (int i = 0; i < 3; i++) {
memset(v, 0, sizeof(v));
for (int j = 0; j < 4; j++) {
if (scanf("%s", str) == 1) {
for (int t = 0; t < 4; t++) {
if (v[str[t]-‘A‘]) flag = true;
v[str[t]-‘A‘] = 1;
for (int k = 0; k < 4; k++) {
if (t == k) continue;
g[str[t]-‘A‘][str[k]-‘A‘]++;
}
g[str[t]-‘A‘][str[t]-‘A‘] = 1;
}
} else
return false;
memcpy(s[i*4+j], str, sizeof(str));
}
}
for (int i = 0; i < 16; i++) {
for (int j = 0; j < 16; j++) {
if (g[i][j] == 0) {
can[i][c[i]++] = j;
}
}
}
memset(v, 0, sizeof(v));
return true;
}
int getX (int* x) {
for (int i = 0; i < 4; i++)
if (v[x[i]] == 1) return x[i];
return -1;
}
void putAns() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
if (j) printf(" ");
printf("%s", s[i*4+j]);
}
printf("\n");
}
for (int k = 0; k < 2; k++) {
for (int i = k; i < 8; i += 2) {
if (i/2) printf(" ");
for (int j = 0; j < 4; j++)
printf("%c", ‘A‘ + ans[i][j]);
}
printf("\n");
}
}
bool judge (int x, int* y) {
for (int i = 0; i < 4; i++)
if (y[i] == x) return false;
return true;
}
bool DFS (int d) {
if (d == 8) {
putAns();
return true;
}
if (d == 0) {
do {
ans[d][0] = 0;
memcpy (ans[d]+1, can[0], sizeof(int)*3);
for (int i = 0; i < 4; i++) v[ans[d][i]]++;
if (DFS(d+1)) return true;
for (int i = 0; i < 4; i++) v[ans[d][i]]--;
} while (next_permutation (can[0], can[0] + c[0]));
} else {
int x = getX(ans[d-1]);
if (x == -1) return false;
int cnt = 1;
ans[d][0] = x;
for (int i = 0; i < c[x]; i++) {
int& u = can[x][i];
if (v[u] < 2 && judge (u, ans[d-1])) {
ans[d][cnt++] = can[x][i];
}
}
if (cnt != 4) return false;
for (int i = 0; i < 4; i++) v[ans[d][i]]++;
if (DFS(d+1)) return true;
for (int i = 0; i < 4; i++) v[ans[d][i]]--;
}
return false;
}
int main () {
while (init ()) {
if (flag || !DFS (0))
printf("It is not possible to complete this schedule.\n");
printf("\n");
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。