GRIDISLANDS - 2

https://www.algospot.com/judge/problem/read/GRIDISLANDS

algospot.com :: GRIDISLANDS

처음 시도했던 백트래킹 방법.

결과는 시간 초과됨ㅜ

 

#include 

int TOP = 1, LEFT = 1, DOWN, RIGHT;
int TOTALBRIDGE, OUTPUT;

int factorial(int n){ int fact = 1; for (int i = 1; i <= n; i++)fact = fact * i; return fact; }
void NUMBER(int start, int direction, int count, int _N, bool down)
{
	if (_N > DOWN)
	{
		OUTPUT += factorial(TOTALBRIDGE - count);
		return;
	}
	if (down)
	{
		NUMBER(start, direction, count + 1, _N + 1, true);

		if (start != LEFT)
			NUMBER(start - 1, 1, count + 1, _N, false);
		if (start != RIGHT)
			NUMBER(start + 1, -1, count + 1, _N, false);
	}
	else // left, right
	{
		if (direction > 0 && start >= LEFT)// LEFT
		{
			NUMBER(start - 1, direction, count + 1, _N, false);
			NUMBER(start, direction, count + 1, _N + 1, true);
		}
		else if (direction < 0 && start <= RIGHT)// RIGHT			
		{
			NUMBER(start + 1, direction, count + 1, _N, false);
			NUMBER(start, direction, count + 1, _N + 1, true);
		}	
	}
	return;
}
int main()
{
	int CASE, N;
	for (scanf("%d", &CASE); CASE > 0; CASE-- )
	{
		scanf("%d", &N);
		OUTPUT = 0;
		DOWN = N; RIGHT = N + 1; TOTALBRIDGE = (2 * N + 1)*((2 * N + 1)/2) + N + 1;

		for (int i = 1; i <= N + 1; i++)
			NUMBER(i, 1, 1, 1, true);
		
		printf("%d\n", OUTPUT % 20090711);
	}
	return 1;
}