1891 사분면 C++

https://www.acmicpc.net/problem/1891

1891번: 사분면

 

이 사분면은 다른 사분면과 다른 특징이 있다.

21

34

라는 구조로 이루어져있고,

깊어질수록 왼쪽에서 오른쪽으로 입력된다.

 

d는 1~50까지 주어지므로

50~1까지 다 입력이 되기때문에 사분면 조각의 번호는 문자열로 받았고,

 

x,y는 2^50 이므로 long long타입으로 받았다.

 

이 사분면은 규칙이 있는데

 

이 사진에서 보면 2의 배수로 증가 또는 감소를 하면서

이동을 하게된다는것

 

그러면 첫 매우 큰 사각형은 2^d-1로 시작을 하면서 문자열마다 체크를 해주고,

만약 범위를 벗어났다면 앞문자열을 변경해주는 방법으로 제귀를 통해 풀었다.

 

앞문자열을 변경하다가 끝에 도달했다면 이동할수없는 구간이므로 -1를 리턴해주었다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
int d;
string dnum;
long long movex, movey;
bool changecheck = false;

void change(int num,int startdnum, bool xy)
{
	//x기준
	if (startdnum <0)
	{
		changecheck = true;
		return;
	}
	if (xy)
	{
		if (dnum[startdnum] == '2')
		{
			if (num == 1)
			{
				dnum[startdnum] = '1';
			}
			else if (num == -1)
			{
				dnum[startdnum] = '1';
				change(num, startdnum - 1, xy);
			}
		}
		else if (dnum[startdnum] == '1')
		{
			if (num == 1)
			{
				dnum[startdnum] = '2';
				change(num, startdnum - 1, xy);
			}
			else if (num == -1)
			{
				dnum[startdnum] = '2';
			}
		}
		else if (dnum[startdnum] == '3')
		{
			if (num == 1)
			{
				dnum[startdnum] = '4';
			}
			else if (num == -1)
			{
				dnum[startdnum] = '4';
				change(num, startdnum - 1, xy);
			}
		}
		else if (dnum[startdnum] == '4')
		{
			if (num == 1)
			{
				dnum[startdnum] = '3';
				change(num, startdnum - 1, xy);
			}
			else if (num == -1)
			{
				dnum[startdnum] = '3';
			}
		}
	}

	//y기준
	else
	{
		if (dnum[startdnum] == '2')
		{
			if (num == 1)
			{
				dnum[startdnum] = '3';
				change(num, startdnum - 1, xy);
			}
			else if (num == -1)
			{
				dnum[startdnum] = '3';
			}
		}
		else if (dnum[startdnum] == '1')
		{
			if (num == 1)
			{
				dnum[startdnum] = '4';
				change(num, startdnum - 1, xy);
			}
			else if (num == -1)
			{
				dnum[startdnum] = '4';
			}
		}
		else if (dnum[startdnum] == '3')
		{
			if (num == 1)
			{
				dnum[startdnum] = '2';
			}
			else if (num == -1)
			{
				dnum[startdnum] = '2';
				change(num, startdnum - 1, xy);
			}
		}
		else if (dnum[startdnum] == '4')
		{
			if (num == 1)
			{
				dnum[startdnum] = '1';
			}
			else if (num == -1)
			{
				dnum[startdnum] = '1';
				change(num, startdnum - 1, xy);
			}
		}
	}

}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> d >> dnum;
	cin >> movex >> movey;
	//dnum바꿀위치
	int startdnum = 0;
	
	while (d)
	{
		long long dpow = pow(2, d-1);
		long long movexcount = movex / dpow;
		long long moveycount = movey / dpow;
		movex = movex % dpow;
		movey = movey % dpow;
		
		change(movexcount, startdnum, true);
		change(moveycount, startdnum, false);
		if (changecheck)
		{
			cout << "-1";
			return 0;
		}
		startdnum++;
		d--;

	}
	cout << dnum;
}