미궁 속의 방

쉽게 생각할 수 있다.

격자 무늬 Square를 생각한다.

다만, 직관적인 Square를 만들기에는 Maximum Size가 M[100000][100000]이므로 적절하지 못하다.

그래서 Function을 생각한다. f( x, y ) -> N을 만든다.

사용자로부터 입력받는 4가지 방향에 따라 Position ( x, y )가 움직일 뿐이므로 아래에선 get 함수로 정의하였다.

마지막으로 Maximum Size일 경우 INT32값을 넘으므로 배열의 자료형은 long long을 사용해서 해결했다.

#define _INT64 long long
using namespace std;
_INT64 A[200000];
int N;
void first()
{
	A[0] = 1;
	int _n = N;
	for (int i = 1; i < 2*N;i++)
		if (i <= N)
		{
			A[i] = (i - 1) + A[i - 1];
		}
		else
		{
			A[i] = _n + A[i - 1];
			--_n;
		}
}
int get(int x, int y)
{
	int C = x + y - 1;
	int R;
	
	if (C > N)
		x -= C - N;

	if (C % 2 == 0)// 짝
		R = A[C + 1] - x;
	else // 홀
		R = A[C] + x - 1;

	return R;
}
int main(int argc, char** argv) {
	int T;
	int test_case;
	/* 아래 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	앞으로 표준 입력(키보드) 대신 input.txt 파일로 부터 읽어오겠다는 의미의 코드입니다.
	만약 본인의 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면,
	그 아래에서 cin 을 사용하여 표준 입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
	따라서 본인의 PC 에서 테스트 할 때에는 아래 주석을 지우고 이 함수를 사용하셔도 됩니다.
	단, 이 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석 처리 하셔야 합니다. */
	//freopen("input.txt", "r", stdin);

	scanf("%d", &T);	//Codeground 시스템에서는 C++ 에서도 scanf 사용을 권장합니다.
	for (test_case = 1; test_case <= T; ++test_case) {
		//	이 부분에서 알고리즘 프로그램을 작성하십시오.

		int K;
		scanf("%d %d", &N, &K);
		int x = 1, y = 1;
		_INT64 R = 0;
		first();

		R += get(x, y);
		getchar();
		for (int i = 0; i < K; i++)
		{
			char v;
			scanf("%c", &v);
			switch (v)
			{
			case 'L':
				--x;
				break;
			case 'R':
				++x;
				break;
			case 'U':
				--y;
				break;
			case 'D':
				++y;
				break;
			}
			R += get(x, y);
		}
		//	이 부분에서 정답을 출력하십시오. Codeground 시스템에서는 C++ 에서도 printf 사용을 권장합니다. 
		printf("Case #%d\n", test_case);
		printf("%lld\n", R);
	}

	return 0;	//	정상종료 시 반드시 0을 리턴해야 합니다.
}