백준 15685번 드래곤 커브

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

N번째 세대에서 방문할 수 있는 (y, x) 를 구하는 방법은 아래와 같다.

1. N-1 번째 세대의 (y, x)에선 N번째 세대에서 쓰일 커브의 방향을 스택에 push 한다.

이후, N번째 세대에선

2. N-1 번째의 마지막 지점을 시작으로 하여 스택에 쌓아둔 커브의 방향대로 (y, x) 를 방문한다.

이를 연속적으로 반복하여 각 세대에서 그려질 수 있는 점들을 방문하고, 마지막엔 특정 (x, y)를 기준으로 3방향을 검사하여 직사각형의 갯수를 구하였다.

#include <cstdio>
#include <vector>
#include <utility>
#define MAX 100
#define RIGHT 0
#define UP 1
#define LEFT 2
#define DOWN 3
using namespace std;
bool map[MAX + 2][MAX + 2] = {false, };
int lastX = 0, lastY = 0;
// 오른쪽, 위쪽, 왼쪽, 아래
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
void visit(int y, int x) {
    if (x >= 0 && x <= MAX && y >= 0 && y <= MAX && !map[y][x]) {
        map[y][x] = true;
    }
}
void dragonCurve(vector<int> ds, int g) {
    // 방향 정보(nd, next direction)
    int nd = ds[0];
    for (int i = 0 ; i < g; ++i) {
        int l = ds.size();
        for (int j = l-1 ; j >= 0; --j) {
            nd = (ds[j] + 1) % 4;
            lastX = lastX + dx[nd];
            lastY = lastY + dy[nd];
            ds.push_back(nd);
            visit(lastY, lastX);
        }
    }
}
int main()
{
    int n, d, g, result = 0;
    scanf("%d", &n);
    
    for (int i = 0 ; i < n; ++i) {
        scanf("%d %d %d %d", &lastY, &lastX, &d, &g);
        map[lastY][lastX] = true;
        
        vector<int> ds;
        ds.push_back(d);
        
        lastX = lastX + dx[d];
        lastY = lastY + dy[d];
        visit(lastY, lastX);
    
        dragonCurve(ds, g);
    }
    
    for (int i = 0; i <= MAX; ++i) {
        for (int j = 0 ; j <= MAX; ++j) {
            if (map[j][i] && map[j][i + 1] && map[j + 1][i + 1] && map[j + 1][i]) {
                result++;
            }
        }
    }
    
    printf("%d\n", result);
    
    return 0;
}