UVa 167 The Sultan's Successors

想法：
    這是一個八皇后問題，可以先將所有可能方式先記下來(共92種)，之後再輸入測資檢查這92種哪一種最大即可，如果還想更快的話，直接把這92種先輸出，然後直接寫在code裡XD。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int P[1000][9];
	int tmp[8];
	int n = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool col[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void func(int r)
	{
	if (r == 8) {
	for (int i = 0; i < 8; ++i)
	P[n][i] = tmp[i];
	++n;
	return;
	}
	for (int c = 0; c < 8; ++c) {
	int ld = (c - r) + 7;
	int rd = c + r;
	if (!col[c] && !left[ld] && !right[rd]) {
	col[c] = 1, left[ld] = 1, right[rd] = 1;
	tmp[r] = c;
	func(r + 1);
	col[c] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	func(0);
	int Case;
	int board[8][8];
	scanf("%d", &Case);
	while (Case--) {
	for (int i = 0; i < 8; ++i)
	for (int j = 0; j < 8; ++j)
	scanf("%d", &board[i][j]);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
	int sum = 0;
	for (int j = 0; j < 8; ++j)
	sum += board[j][P[i][j]];
	if (sum > ans) ans = sum;
	}
	printf("%5d\n", ans);
	}
	}

view raw UVa 167 The Sultan's Successors.cpp hosted with ❤ by GitHub