15686 드래곤 커브

15686 드래곤 커브

시뮬레이션 문제이다.

90도 회전하는 규칙을 찾는게 중요한데 나는 무식하게 찾았다.

(x,y) 가 기준좌표 일 때 (ax, ay) 를 90도 회전한 좌표구하기

기준좌표와 목표좌표의 차 dx, dy

dx = x - ax;

dy = y - ay;

90도 회전된 좌표 nx, ny

nx = x + (-1)*dy

ny = y + dx

이다.

정사각형 찾을때는 현재좌표/오른쪽/아래/오른대각아래 4꼭지점이 다 있으면 +1 해주었다.

#include <iostream>
#include <vector>
#include <algorithm>
#define P pair<int,int>
using namespace std;
 
int n, x, y, d, g, nx, ny;
int map[102][102];
int dx[] = { 0,-1, 0,1 };
int dy[] = { 1,0,-1,0 };
vector<P> v;
 
void printAll() {
    cout << endl;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}
 
//꼭지점 4개가 뭉쳐있으면 정사각형 한칸이다.
int get_result() {
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j]!=0 && map[i + 1][j]!=0 && map[i][j + 1]!=0 && map[i + 1][j + 1]!=0) {
                ans++;
            }
        }
    }
    return ans;
}
 
void solve(int val) {
    int ax, ay;
 
    int sz = v.size();
    for (int i = 0; i < sz; i++) {
        //90도 회전된 좌표
        ax = nx + (-1)*(ny - v[i].second);
        ay = ny + nx - v[i].first;
        
        if (map[ax][ay] == val) continue;
        map[ax][ay] = val;
        v.push_back(P(ax, ay));
    }
    //다음 기준점은 현재 기준점에서 제일 처음 찍힌점을 90도 회전한 위치이다.
    ax = (nx - x);
    ay = (-1)*(ny - y);
    nx = nx + ay;
    ny = ny + ax;
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> y >> x >> d >> g;
        v.clear();
 
        v.push_back(P(x, y));
        map[x][y] = i;
 
        nx = x + dx[d];
        ny = y + dy[d];
        v.push_back(P(nx, ny));
        map[nx][ny] = i;
 
        //세대 만큼 회전시키기 
        while (g--) {
            solve(i);
        }
    }
 
    //printAll();
    cout << get_result() << endl;
}