백준 15685번 드래곤 커브 C++

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

 

어떤 점을 중심으로 시계방향으로 90도 회전했을 때의 좌표를 구하는 방법만 생각해낸다면 쉽게 풀 수 있는 문제이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int dX[4] = { 1,0,-1,0 };
int dY[4] = { 0,-1,0,1 };

vector<vector<bool>> board(101, vector<bool>(101, false));
vector<vector<pair<int, int>>> dragons;
vector<bool> isValid;
vector<int> currGeneration;
vector<int> targetGeneration;

pair<int, int> convertPos(pair<int, int> &centor, pair<int, int> &pos) {
    int x = pos.first - centor.first;
    int y = pos.second - centor.second;
    ::swap(x, y);
    x = -x;
    x += centor.first;
    y += centor.second;

    return ::make_pair(x, y);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    dragons = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());
    isValid = vector<bool>(n, true);
    currGeneration = vector<int>(n, 0);
    targetGeneration = vector<int>(n, 0);

    for (int i = 0; i < n; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        dragons[i].push_back({ x,y });
        board[y][x] = true;
        int nextX = x + dX[d];
        int nextY = y + dY[d];
        if (nextX < 0 || nextX>100) continue;
        if (nextY < 0 || nextY>100) continue;
        dragons[i].push_back({ nextX,nextY });
        board[nextY][nextX] = true;
        targetGeneration[i] = g;
    }
    
    for (int i = 0; i < n; i++) {
        while (currGeneration[i] < targetGeneration[i]) {
            int lastIdx = dragons[i].size() - 1;
            pair<int, int> centor = dragons[i][lastIdx];

            vector<pair<int, int>> addPoses;

            for (int j = lastIdx - 1; j >= 0; j--) {
                addPoses.push_back(convertPos(centor, dragons[i][j]));
            }

            for (auto a : addPoses) {
                dragons[i].push_back(a);
                board[a.second][a.first] = true;
            }

            currGeneration[i]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            bool check1 = board[i][j];
            bool check2 = board[i + 1][j];
            bool check3 = board[i][j + 1];
            bool check4 = board[i + 1][j + 1];
            if (check1 && check2 && check3 && check4)
                ans++;
        }
    }
    cout << ans;
}