NQEEN

https://algospot.com/judge/problem/read/NQUEEN

algospot.com :: NQUEEN

완전 탐색을 진행함.

N*N의 탐색은 TimeOut

QEEN의 특성으로 한 줄에는 1개의 QEEN이 놓아져야함. 그래서 N까지 탐색하면 됨.

 

#include 
#include 

int MAP[13][13];
int N, VALUE;

bool INPUT(bool type,int c, int r)
{
	if (type && MAP[c][r] != 0)
		return 0;

	for (int i = -N; i < N; i++)
	{
		int _h = c + i;
		int _g = r + i;
		int _j = -(-c + i);

		if ((_h != c) && _h >= 0 && _h < N)
			(type) ? ++MAP[_h][r] : --MAP[_h][r];
		if ((_g != r) && _g >= 0 && _g < N)
			(type) ? ++MAP[c][_g] : --MAP[c][_g];
		if ((_h != c && _g != r) && (_h >= 0 && _h < N) && (_g >= 0 && _g < N))
			(type) ? ++MAP[_h][_g] : --MAP[_h][_g];
		if ((_j != c && _g != r) && (_j >= 0 && _j < N) && (_g >= 0 && _g < N))
			(type) ? ++MAP[_j][_g] : --MAP[_j][_g];
	}
	(type) ? ++MAP[c][r] : --MAP[c][r];
	return 1;
}

void RESULT(int INDEX, int COUNT)
{
	if (COUNT == N + 1)
	{
		++VALUE;
		return; 
	}

	for (int i = (INDEX / N) * N; i < (INDEX / N + 1) * N && i < (N*N); i++)
	{
		if (INPUT(1, i / N, i % N))
		{
			RESULT(i + N, COUNT + 1);
			INPUT(0, i / N, i % N);
		}
	}
	return;
}
int main()
{
	int CASE;
	
	for (scanf("%d", &CASE); CASE > 0; CASE--)
	{
		scanf("%d", &N);
		memset(MAP, 0, sizeof(MAP));
		VALUE = 0;

		RESULT(0, 1);

		printf("%d\n", VALUE);
	}

	return 0;
}