《算法竞赛入门经典》上的八皇后问题,回溯。还是递归的运用。
#include<cstdio> #include<cstring> using namespace std; int maze[8][8],c[100],max,n=8; void search(int cur) { int i,j; if(cur==n) { int sum=0; for(i=0; i<n; i++) sum+=maze[i][c[i]]; max=max>sum?max:sum; } else for(i=0; i<n; i++) { int ok=1; c[cur]=i; for(j=0; j<cur; j++) if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]) { ok=0; break; } if(ok) search(cur+1); } } int main() { /*freopen("in.txt","r",stdin);*/ int k; scanf("%d",&k); while(k--) { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) scanf("%d",&maze[i][j]); } max=0; int cur=0; search(cur); printf("%5d\n",max); } return 0; }