BOJ15685: 드래곤 커브

풀이

dragoncurve()함수는 각 드래곤 커브의 방향을 계산하여, 좌표를 curve_cor에 저장
다음 세대의 드래곤 커브의 방향은 이전 세대 드래곤 커브의 순서를 반대로 하여 시계방향으로 회전시킨 것

위 그림과 같은 드래곤 커브에서 direction = {0, 1, 2, 1, 2, 3, 2, 1}이 되고 (0,0)에서부터 direction에 맞추어 이동하면 모든 좌표를 구할 수 있다.
curve_cor에 저장된 모든 드래곤 커브의 모든 좌표를 왼쪽, 위쪽의 점이라고 생각하고 생길 수 있는 정사각형의 개수를 센다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

vector<int> dragon;
queue<pair<int,int>> curve_cor;
int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
bool cordinate[102][102]={{false,}};

int check_square(){
    int cnt(0);
    bool visit[102][102]={{false,}};
    while(!curve_cor.empty()){
        int x=curve_cor.front().first, y=curve_cor.front().second;
        curve_cor.pop();
        if(y>= 100 | x >= 100) continue;
        if(!visit[y][x] && cordinate[y+1][x] && cordinate[y][x+1] && cordinate[y+1][x+1]) cnt++;
        visit[y][x] = true;
    }

    return cnt;
}

void dragoncurve(int x, int y, int d, int g){
    vector<int> direction;
    vector<pair<int,int>> cor;
    direction.reserve((1<<g));
    cor.reserve((1<<g)+1);
    direction.push_back(d);
    cor.push_back(make_pair(x,y));
    curve_cor.push(make_pair(x,y));
    cordinate[y][x] = true;

    for(int gg(0); gg < g; gg++){
        for(int i((1<<gg)-1); i >= 0; i--){
            direction.push_back((direction[i]+1)%4);
        }
    }

    for(int i(0); i < (1<<g); i++){
        cor.push_back(make_pair(cor[i].first+dx[direction[i]], cor[i].second+dy[direction[i]]));
        curve_cor.push(make_pair(cor[i].first+dx[direction[i]], cor[i].second+dy[direction[i]]));
        cordinate[cor[i].second+dy[direction[i]]][cor[i].first+dx[direction[i]]] = true;
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    int N, tmp;
    cin >> N;
    dragon.reserve(4*N+1);
    for(int n(0); n < N; n++){
        for(int i(0); i < 4; i++){
            cin >> tmp;
            dragon.push_back(tmp);
        }
    }

    for(int n(0); n < N; n++){
        dragoncurve(dragon[4*n],dragon[4*n+1],dragon[4*n+2],dragon[4*n+3]);
    }

    cout << check_square();

    fclose(stdin);
    return 0;
}

BOJ15685: 드래곤 커브

Categories

Tags