UVa 11085 Back to the 8-Queens

想法：
    先建表，把可能的位置存下來(共92種)，然後再看哪種位置所需要的Move數量最低。話說原本不知道Queen原來像象棋的車，移動一步可以任意距離，害我吃了WA@_@

	#include <cstdio>
	#include <vector>
	using namespace std;
	int Container[8];
	int Queens_row[100][8];
	int nOfQueens = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool row[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void Eight_Queens(int c)
	{
	if (c == 8) {
	for (int i = 0; i < 8; ++i)
	Queens_row[nOfQueens][i] = Container[i] + 1; //+1是因為題目的row是從1開始
	++nOfQueens;
	return;
	}
	for (int r = 0; r < 8; ++r) {
	int ld = c - r + 7;
	int rd = c + r;
	if (!row[r] && !left[ld] && !right[rd]) {
	row[r] = 1, left[ld] = 1, right[rd] = 1;
	Container[c] = r;
	Eight_Queens(c + 1);
	row[r] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	Eight_Queens(0);
	int row_position[8], Case = 1;
	while (scanf("%d", &row_position[0]) != EOF) {
	for (int i = 1; i < 8; ++i)
	scanf("%d", &row_position[i]);
	int Min = 99999;
	for (int i = 0; i < nOfQueens; ++i) {
	int Move = 0;
	for (int c = 0; c < 8; ++c)
	if (Queens_row[i][c] != row_position[c])
	++Move;
	if (Move < Min) Min = Move;
	}
	printf("Case %d: %d\n", Case++, Min);
	}
	}

view raw [UVa] 11085 Back to the 8-Queens.cpp hosted with ❤ by GitHub