八皇后问题(C语言)

传送门：https://nanti.jisuanke.com/t/381

错误案例

#include 
#include
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
#include
int mp[10][10], k, lie[10], zheng[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] && !zheng[x-i+n] && !ci[x+i]) {//同列没有，左上到右下(15斜行)没有，右上到左下没有 
			//放棋子，标记一下 
			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(zheng, 0, sizeof(zheng));
		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("%dn", max);
	}
}