15685 드래곤 커브 (c++)

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

15685번: 드래곤 커브

 

커브를 구하는 것을 먼저한다.

각 방향 전환수는 2 ^ stage no 번이다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


struct Dragon {
	int x, y, d, g;
};

int n, res;
vector <Dragon> dragon;
int map[101][101];

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



void solve() {

	for(int i=0; i<dragon.size(); i++) {

		int curve_size = 0;
		int curve[1025] = {0, };

		// check start point
		Dragon d = dragon[i];
		int new_y = d.y;
		int new_x = d.x;
		int new_d = d.d;
		curve[curve_size++] = d.d;
		map[new_y][new_x] = 1;
		
        // 세대 , 방향구하기
		for (int j=0; j<d.g; j++) 
			for(int k=curve_size-1; k>=0; k--) {
				curve[curve_size++] = (curve[k] +1) % 4;
			}

		for(int j=0; j<curve_size; j++) {
			new_y += dy[curve[j]];
			new_x += dx[curve[j]];

			if(new_y < 0 || new_y >= 101|| new_x < 0 || new_x >= 101) continue;

			map[new_y][new_x] = 1;
		}
		
	}

}

void count_box() {

    for (int y = 0; y < 100; ++y) {
        for (int x = 0; x < 100; ++x) {
            if (map[y][x] && map[y][x + 1] && map[y + 1][x] && map[y + 1][x + 1]) {
                ++res;
            }
        }
    }

}

int main() {
	scanf("%d", &n);

	for(int i=0; i<n; i++) {
		Dragon tmp;
		scanf("%d %d %d %d" , &tmp.x, &tmp.y, &tmp.d, &tmp.g);
		dragon.push_back(tmp);
	}

	solve();
	count_box();

	printf("%d\n", res);


}

3
3 3 0 1
4 2 1 3
4 2 2 1

>> 4

 

 

 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)