15685 드래곤 커브

드래곤 커브의 특성을 직접 그려보면

끝점을 기준으로 시계방향으로 90도 돌린다는 말의 의미를 알 수 있다.

을 n세대 i번째 선분이라고 할 때 

가 됨을 알 수 있다.

또한 선분의 양끝점을 저장할 필요 없이 움직인 방향만 기록해놓고

dx[], dy[]를 시계방향 혹은 반시계방향으로 해놓는다면 (저장된 방향 + 시작방향)%4 로 간단하게 계산이 가능하다.

#include <stdio.h>
 
int main() {
    int a[1 << 12] = { 0, };
    int map[101][101] = { 0, };
    int dx[] = { 1,0,-1,0 }, dy[] = { 0,-1,0,1 };
 
    for (int i = 1, cur = 2; i <= 10; i++, cur <<= 1) for (int j = cur / 2; j < cur; j++) 
        a[j] = (a[cur - j - 1] + 1) % 4;
 
    int n;
    scanf("%d", &n);
    while (n--) {
        int x, y, d, g;
        scanf("%d%d%d%d", &x, &y, &d, &g);
        map[y][x] = 1;
        for (int i = 0; i < 1 << g; i++) {
            x += dx[(a[i] + d)%4];
            y += dy[(a[i] + d)%4];
            map[y][x] = 1;
        }
    }
    int res = 0;
    for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++)
        res += map[i][j] & map[i + 1][j] & map[i][j + 1] & map[i + 1][j + 1];
    printf("%d\n", res);
    return 0;
}