167 - The Sultan's Successors（八皇後問題（回溯））

題目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;
}