백준 15685 / 드래곤 커브

규칙 찾기가 중요한 문제

1세대 드래곤 커브가 (0,0)에서 그려질때, 방향을 나열하면

0,1

2세대 드래곤 커브의 경우엔

0,1,2,1

3세대 드래곤 커브의 경우

0,1,2,1,2,3,2,1

0,1,2,1과 2,3,2,1을 비교하면

0,1,2,1를 거꾸로 한 1,2,1,0에서

1을 추가하니 2,3,2,1이됨을 확인할 수 있다.

이 규칙을 찾으려면.. 음.....

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int map[101][101];
 
vector<pair<int, int>>dim;
 
int n;
 
deque<int>tmp;
 
bool first;
 
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
 
void makedir(int gen) {
    if (gen == 0) {
        return;
    }
    for (int i = tmp.size() - 1; i >= 0; i--) {
        int dir = tmp[i];
        dir++;
        if (dir == 4) {
            dir = 0;
        }
        tmp.push_back(dir);
    }
    makedir(gen - 1);
}
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        first = true;
 
        int x, y, dir, gen;
        cin >> x >> y >> dir >> gen;
 
        tmp.clear();
        tmp.push_back(dir);
        makedir(gen);
        map[x][y] = 1;
        for (int k = 0; k < tmp.size(); k++) {
            int nx = x + dx[tmp[k]];
            int ny = y + dy[tmp[k]];
 
            map[nx][ny] = 1;
            x = nx;
            y = ny;
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j] == 1 && map[i + 1][j + 1] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}