题目167 - The Sultan's Successors
题目大意：就是八皇后的问题，只是加上求八个皇后所对应的位置对应的值相加的最大值。
阶梯思路：八皇后问题转换成全排列问题，C【i】 = j 表示第i行 的皇后在第j列，这样排列的话每行的皇后不会互相冲突，就需要判断每列的皇后和两条对角线是否有冲突的皇后，所以这需要开一个数组vis【3】【MAXN】， 每次判断vis【0】【j】（第j列有没有皇后存在） vis【1】【cur + j】 副对角线上是否存在皇后，vis【2】【j - cur + n】 主对角线上是否存在皇后。
#include#include const int N = 8; int chess[N][N], vis[3][2 * N], c[N]; int t, sum; void handle (int cur) { if ( cur == N) { int s = 0; for (int i = 0; i < N; i++) s += chess[i][c[i]]; if ( sum < s) sum = s; } for ( int i = 0; i < N; i++) { if (!vis[0][i] && !vis[1][i + cur] && ! vis[2][i - cur + N]) { c[cur] = i; vis[0][i] = vis[1][i + cur] = vis[2][i - cur + N] = 1; handle(cur + 1); vis[0][i] = vis[1][i + cur] = vis[2][i - cur + N] = 0; } } } int main () { scanf("%d", &t); while (t--) { for (int i = 0; i < N; i++ ) for (int j = 0; j < N; j++ ) scanf("%d", &chess[i][j]); memset(vis, 0, sizeof(vis)); sum = 0; handle(0); printf("%5d\n", sum); } return 0; }