[BOJ] 15685 : ๋๋๊ณค ์ปค๋ธ
๋ฌธ์ ๋งํฌ
15685๋ฒ: ๋๋๊ณค ์ปค๋ธ (acmicpc.net)
15685๋ฒ: ๋๋๊ณค ์ปค๋ธ
์ฒซ์งธ ์ค์ ๋๋๊ณค ์ปค๋ธ์ ๊ฐ์ N(1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๋ ๋ค ์ ์ x, y, d, g๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. x์ y๋ ๋๋๊ณค ์ปค
www.acmicpc.net
๋จ์ํ ๊ตฌํ ๋ฌธ์ .
ํ์ด
ํ ์ ์์ ์์๋ ์ปค๋ธ๋ฅผ ํ ์ธ๋๋ง๋ค ์๊ณ๋ฐฉํฅ์ผ๋ก 90๋ ํ์ ํ์ฌ ์ด์ด๋ถ์ธ ๋ชจ์์ ๋๋๊ณค ์ปค๋ธ๋ผ๊ณ ํ๋ค.
๋๋ ํ ์ธ๋ ํ ์ธ๋ ์ง๋ ๋๋ง๋ค ์ปค๋ธ๋ฅผ ๊ทธ๋ฆฌ๋ ๊ฒ์๋๋ผ g๋ฒ์งธ ์ธ๋๊น์ง ๊ทธ๋ ธ์ ๋ ์ปค๋ธ์ ๋ฐฉํฅ์ ๋ฒกํฐ์ ์ ์ฅํด๋๊ณ ํ๋ฒ์ ๊ทธ๋ฆฌ๋ ๋ฐฉ์์ผ๋ก ์งํํ๋ค.
์ฒ์์ ์ปค๋ธ๋ฅผ ์ง์ ๊ทธ๋ ค๋ณด๋ฉด์ ๊ท์น์ ํ์ ํ๋ค.
์๊ณ๋ฐฉํฅ์ผ๋ก 90๋ ํ์ ํ ํ ์ปค๋ธ์ ์งํ๋ฐฉํฅ์ ์ด๋ป๊ฒ ๋ฐ๋๋์ง ์ดํด๋ณด๋ฉด
1. x์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (→) ์ ํ์ ํ y์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (↑) ์ผ๋ก ๋ฐ๋๋ค.
2. y์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (↑) ์ ํ์ ํ x์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (←) ์ผ๋ก ๋ฐ๋๋ค.
3. x์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (←) ์ ํ์ ํ y์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (↓) ์ผ๋ก ๋ฐ๋๋ค.
4. y์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (↓) ์ ํ์ ํ x์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (→) ์ผ๋ก ๋ฐ๋๋ค.
์ด ๊ท์น์ ์ด์ฉํด์ g์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ฅผ ์ด๋ฃจ๋ ์งํ๋ฐฉํฅ์ ์์๋๋ก ๋ฒกํฐ์ ์ ์ฅํ๋ค.
๋จ, ๊ธฐ์กด์ ์ ์ฅ๋ ๋ฐฉํฅ์ ํ์ ํ์ ์ด์ด๋ถ์ด๋ ๊ฒ์ฒ๋ผ ๊ตฌํํ๋ ค๋ฉด ๊ธฐ์กด์ ๋ฒกํฐ์์ ๋ค์์ ๋ถํฐ ๊ฐ์ ๊บผ๋ด ํ์ ํ ํ๋ฒกํฐ์ ์ถ๊ฐํด์ฃผ์ด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด ์์์ ๋์จ 3์ธ๋ ๋๋๊ณค ์ปค๋ธ๋
(0,0)์์ ์์ํด์
→ ,↑, ← ,↑, ← ,↓, ← ,↑ ์์๋๋ก ์งํํ๋ฉด 3์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ฅผ ๊ทธ๋ฆด ์ ์๋ค.
์ด ๋ฐฉํฅ์ ๋ฒกํฐ์ ์ ์ฅํ ํ ํ ๋ฒ์ ๊ทธ๋ ค์ฃผ์๋ค. ๋ฒกํฐ์ ์ ์ฅ๋ ๋ฐฉํฅ ์์๋๋ก ์ด๋ํ๋ฉด์ ๋๋๊ณค ์ปค๋ธ์ ํฌํจ๋๋ ์ขํ๋ visited๋ฐฐ์ด์ true๋ก ํ์ํ๋ค.
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
42
43
44
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
bool Map[MAX_N][MAX_N];
int N;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
void dragon_curve(int x, int y, int d, int g);
bool is_ans(int x, int y) {
if (Map[x][y] && Map[x + 1][y] && Map[x][y + 1] && Map[x + 1][y + 1])
return true;
return false;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
int x, y, d, g;
cin >> x >> y >> d >> g;
dragon_curve(x, y, d, g);
}
int ans = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (is_ans(i, j))
ans++;
}
}
cout << ans << "\n";
return 0;
}
int change_direction(int d) {
if (d == 0) return 1;
else if (d == 1) return 2;
else if (d == 2) return 3;
else if (d == 3) return 0;
}
void dragon_curve(int x, int y, int d, int g) {
vector<int> direction;
direction.push_back(d);
for (int i = 1; i <= g; i++) { //generation
for (int j = direction.size() - 1; j >= 0; j--) {
direction.push_back(change_direction(direction[j]));
}
}
Map[x][y] = true;
for (int i = 0; i < direction.size(); i++) {
x += dx[direction[i]];
y += dy[direction[i]];
Map[x][y] = true;
}
}
|
cs |
๊ทธ๋ฆฌ๊ณ ๋ง์ฝ ํ ๋ณ์ ๊ธธ์ด๊ฐ 1์ธ ์ ์ฌ๊ฐํ ๋ค ๊ผญ์ง์ ์ด ๋ชจ๋ true๋ก ํ์๋์ด์์ผ๋ฉด ๊ทธ ์ ์ฌ๊ฐํ์ ๋๋๊ณค ์ปค๋ธ์ ํฌํจ๋ ๊ฒ์ผ๋ก ์ธ์งํ๋ค.