2197.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2197 on 2006-07-23 at 15:55:00 */ 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAX = 320;

bool vst[3][2*MAX];
int x[MAX], n;

void queen();
bool posQueen(int);
bool find(int);

int main()
{
	int t, T;

	scanf("%d", &T); srand(1040310411);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		queen();
	}
	
	return 0;
}

void queen()
{
	int i, rn = n * 19 / 20;
	while(!posQueen(rn) || !find(rn)) ;
	printf("%d\n", n);
	for(i = 0; i < n; i++) printf("%d%c", x[i], (i == n-1) ? '\n' : ' ');
}
bool posQueen(int m)
{
	memset(vst, false, sizeof(vst));
	int i, j, vp[MAX];
	for(i = 0; i < m; i++) {
		int vn = 0;
		for(j = 0; j < n; j++)
			if(!vst[0][j] && !vst[1][j+i] && !vst[2][i-j+n])
				vp[vn++] = j;
		if(vn == 0) return false;
		x[i] = vp[rand()%vn];
		vst[0][x[i]] = vst[1][x[i]+i] = vst[2][i-x[i]+n] = true;
	}
	return true;
}
bool find(int r)
{
	if(r == n) return true;
	int i;
	for(i = 0; i < n; i++) {
		if(vst[0][i] || vst[1][i+r] || vst[2][r-i+n]) continue;
		vst[0][i] = vst[1][i+r] = vst[2][r-i+n] = true; x[r] = i;
		if(find(r+1)) return true;
		vst[0][i] = vst[1][i+r] = vst[2][r-i+n] = false;
	}
	return false;
}