BOJ 15685: 드래곤 커브

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (25/187)
  • 문제를 잘읽자를 10번 복창한다.
  • 어이없게 사면이 모두 면으로 막혀있는 경우를 찾는줄 알고, grid 자료구조를 만들고 삽질을 엄청나게 함.
  • 4점 모두 찍혀있는 경우는 훨씬 더 간단하게 풀 수 있음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int N;
const int SZ = 100;
int board[SZ+1][SZ+1];
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0,-1, 0, 1};
int curve[1024] = {0,1};

void makeCurve() {
  for(int i = 1; i < 10; i++) {
    int a = 1 << i;
    int b = 3 << (i-1);
    for(int j = 0; j < b-a; j++) {
      curve[a+j] = (2+curve[j])%4;
      curve[b+j] = curve[b-a+j];
    }
  }
}

int main() {
  makeCurve();
  cin >> N;
  for(int i = 0; i < N; i++) {
    int x, y, d, g;
    cin >> x >> y >> d >> g;
    board[x][y] = 1;
    for(int j = 0; j < 1<<g; j++) {
      int dir = (d + curve[j])%4;
      x += dx[dir], y += dy[dir];
      board[x][y] = 1;
    }
  }

  int ans = 0;
  for(int i = 0; i < SZ; i++)
    for(int j = 0; j < SZ; j++)
      ans += (board[i][j] && board[i][j+1] && board[i+1][j] && board[i+1][j+1]);
  cout << ans;
}