传送门:https://nanti.jisuanke.com/t/381
错误案例
#include<stdio.h>
#include<string.h>
int q[10][10], vis[10], lie[20], zd[50], cd[50], k, cnt;
int sum(int t[]) {
int p = 0;
for (int i = 0; i < 8; i++) {
p += t[i];
}
return p;
}
void dfs(int sp) {
if (sp == 8) {
if (sum(vis) > cnt) cnt = sum(vis);
return ;
}
for (int i = 0; i < 8; i++) {
if (!lie[i] && !zd[sp - i + 8] && !cd[sp + i]) {
lie[i] = 1;
zd[sp - i + 8] = 1;
cd[sp + i] = 1;
vis[i] = q[sp][i];
dfs(sp + 1);
lie[i] = 0;
zd[sp - i + 8] = 0;
cd[sp + i] = 0;
}
}
return ;
}
int main() {
scanf("%d", & k);
while(k--) {
// memset(lie, 0, sizeof(lie));
// memset(zd, 0, sizeof(zd));
// memset(cd, 0, sizeof(cd));
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
scanf("%d", & q[i][j]);
}
}
dfs(0);
printf("%d", cnt);
if (k > 1)printf("\n");
}
}
正确答案:
#include<stdio.h>
#include<string.h>
int mp[10][10], k, lie[10], xie[40], ci[40], max, a[10], n=8;
void dfs(int x, int r) {
if (r == 0) {
int sum=0;
for (int i = 1; i <= n; i++ ) {
sum += a[i];
}
if(sum > max) max = sum;
return ;
}
if(x > n)return;
for (int i = 1; i <= n; i++) {
if (!lie[i] && !xie[x-i+n] && !ci[x+i]) {
lie[i] = 1;
xie[x-i+n] = 1;
ci[x+i] = 1;
a[x] = mp[x][i];
r--;
dfs(x+1, r);
lie[i] = 0;
xie[x-i+n] = 0;
ci[x+i] = 0;
a[x] = 0;
r++;
}
}
}
int main() {
scanf("%d", & k);
while (k--) {
max = 0;
memset(lie, 0, sizeof(lie));
memset(xie, 0, sizeof(xie));
memset(ci, 0, sizeof(ci));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", & mp[i][j]);
}
}
dfs(1, 8);
printf("%d\n", max);
}
}