[BOJ 15685] 드래곤 커브

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

15685번: 드래곤 커브

---

[0, 100] 내에서 사각형의 4개의 점이 드래곤 커브의 일부인 사각형의 개수를 찾는 문제이다.

 

드래곤 커브를 모두 그린 다음에 좌표내에 위 조건을 만족하는 사각형이 몇 개 있는지를 확인하면 되는 문제이다.

 

드래곤 커브를 그리는 방법은 

배열에 이전까지의 드래곤 커브의 정보를 저장한 후, 

세대마다 해당 정보로 다음 세대를 만들면 된다.

 

마지막에 0부터 100 사이에 조건을 만족하는 사각형의 개수를 찾으면 된다.

---

#include <stdio.h>
#include <stdlib.h>

int D[101][101];


void DC(int x, int y, int d, int _g)
{
	int arr[1024];
	int _i = 0;

	D[y][x] = 1;
	arr[_i] = d;
	_i++;
	switch (d)
	{
	case 0:
		x++;
		break;
	case 1:
		y--;
		break;
	case 2:
		x--;
		break;
	case 3:
		y++;
		break;
	}
	D[y][x] = 1;

	for (int g = 0; g < _g; g++)
	{
		int __i = _i;
		for (int i = __i - 1; i >= 0; i--)
		{
			switch ((arr[i] + 1) % 4)
			{
			case 0:
				x++;
				break;
			case 1:
				y--;
				break;
			case 2:
				x--;
				break;
			case 3:
				y++;
				break;
			}
			D[y][x] = 1;
			arr[_i] = (arr[i] + 1) % 4;
			_i++;
		}
	}
	
}

int main()
{
	int N;
	int x, y, d, g;
	int sum = 0; 

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d %d %d", &x, &y, &d, &g);
		DC(x, y, d,g);
	}

	for (int x = 0; x <= 100; x++)
	{
		for (int y = 0; y <= 100; y++)
		{
			int flag = 1;
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 2; j++)
				{
					if (D[y + j][x + i] != 1)
					{
						flag = 0;
						break;
					}
				}
				if (!flag)
					break;
			}
			if (flag)
				sum++;
		}
	}

	printf("%d", sum);
}