[백준 15685] 드래곤 커브

문제

www.acmicpc.net/problem/15685

 

알고리즘

implementation

 

풀이

드래곤 커브들이 주어졌을 때, 네 모서리가 모두 드래곤 커브인 1x1 사각형의 갯수를 구하는 문제입니다.

 

다음 세대가 시작할 때, 이전세대에서 사용했던 방향 + 1로 드래곤 커브를 진행합니다. 이때 이전세대의 마지막 부분부터 이전세대의 첫 부분 순으로 다음 세대의 처음부터 다음 세대의 마지막부분의 방향을 결정합니다. 이를 관찰하여 구현해 풀면 되는 문제입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int dy[4] = { 0, -1, 0, 1 };
const int dx[4] = { 1, 0, -1, 0 };

int N, ans;
bool board[105][105];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        board[y][x] = true;
        int dir[1024] {};
        dir[0] = d;
        y = y + dy[d];
        x = x + dx[d];
        board[y][x] = true;
        int cnt = 0;
        for (int j = 0; j < g; ++j) {
            for (int k = pow(2, j) - 1; k >= 0; --k) {
                int nx = x + dx[(dir[k] + 1) % 4];
                int ny = y + dy[(dir[k] + 1) % 4];

                x = nx;
                y = ny;
                board[y][x] = true;
                dir[++cnt] = (dir[k] + 1) % 4;
            }
        }
    }
    rep(i, 100) rep(j, 100) {
        if (board[i][j] && board[i + 1][j] && board[i][j + 1] && board[i + 1][j + 1]) {
            ans += 1;
        }
    }
    cout << ans;
    return 0;
}