드래곤 커브 (feat. 백준, 15685번)

드래곤 커브
https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

반응형

// woohyeon.kim
#include <iostream>
#include <vector>

using namespace std;

int N;
int arr[101][101];
int dx[4], dy[4];
int pos_x, pos_y, direction, generation;
vector<int> status;

void make_dragon(int g)
{
	if (g > generation)		return;
	if (g == 0){
		arr[pos_x][pos_y] = 1;
		pos_x = pos_x + dx[direction], pos_y = pos_y + dy[direction];
		arr[pos_x][pos_y] = 1;
		status.push_back(direction);
		make_dragon(g + 1);
	}
	else{
		for (auto idx = static_cast<int>(status.size() - 1); idx >= 0; --idx){
			direction = (status[idx] + 1) % 4;
			pos_x = pos_x + dx[direction], pos_y = pos_y + dy[direction];
			arr[pos_x][pos_y] = 1;
			status.push_back(direction);
		}
		make_dragon(g + 1);
	}
}

inline const bool is_rectangle(int& x, int& y)
{
	if (arr[x][y] != 1)			return false;
	if (arr[x + 1][y] != 1)		return false;
	if (arr[x][y + 1] != 1)		return false;
	if (arr[x + 1][y + 1] != 1)	return false;
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	// 0 : 동, 1 : 북, 2 : 서, 3 : 남
	dx[0] = 0, dx[1] = -1, dx[2] = 0, dx[3] = 1;
	dy[0] = 1, dy[1] = 0, dy[2] = -1, dy[3] = 0;
	cin >> N;
	for (auto idx = 0; idx < N; ++idx){
		cin >> pos_y >> pos_x >> direction >> generation;
		make_dragon(0);
		status.clear();
	}

	auto result = 0;
	for (auto ix = 0; ix <= 100; ++ix)
		for (auto iy = 0; iy <= 100; ++iy)
			if (is_rectangle(ix, iy))	++result;
	cout << result << endl;
	return 0;
}
// *&)*@*

1. 다음 세대가 되면 기존의 모든 정보는 시계방향으로 돌아갑니다.
2. 따라서 가장 마지막에 저장된 노드의 점으로부터 시계방향으로 돌려주면 됩니다.