[伯俊]15685号龍曲線(C++、三星機出)
18822 ワード
https://www.acmicpc.net/problem/15685
これは簡単な実施問題である.
方向を基準にストレージと解凍を行いました.
絵をよく見ると規則正しい.
加齢に伴い、前世代画の逆順で90度(方向+1)回転すればよい.
例えば、第2世代から0 1 2 1で行う.
次世代の第3世代では、0 1 2 1の逆順で1 2 1 0を後ろに貼り、この値の1に1つの値(90度回転)を加えればよい.
コードは以下の通りです.
現在の情報は次世代で使用する必要があるのでvectorに入れて次世代に渡します.
コードは以下の通りです.
これは簡単な実施問題である.
方向を基準にストレージと解凍を行いました.
絵をよく見ると規則正しい.
加齢に伴い、前世代画の逆順で90度(方向+1)回転すればよい.
例えば、第2世代から0 1 2 1で行う.
次世代の第3世代では、0 1 2 1の逆順で1 2 1 0を後ろに貼り、この値の1に1つの値(90度回転)を加えればよい.
コードは以下の通りです.
if (depth != 0) {
for (int i = v.size() - 1; i >= 0; i--) {
q.push((v[i] + 4 + 1) % 4);
}
}
次に、キューに格納されている値をポップアップし、移動してmapに表示します.現在の情報は次世代で使用する必要があるのでvectorに入れて次世代に渡します.
コードは以下の通りです.
int nx = x; int ny = y;
while (!q.empty()) {
// 큐에 있는 값으로 이동을 해주면서 map에 표시
// 다음 세대에 현재까지의 정보가 필요하므로
// vector에 담아 다음 세대에 전달
int direction = q.front();
v.push_back(direction);
q.pop();
nx += dir[direction][0];
ny += dir[direction][1];
map[ny][nx] = 1;
}
完全なコード
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
int dir[4][2] = { {1,0}, {0,-1}, {-1,0}, {0,1} };
int map[101][101];
int answer = 0;
// 정사각형이 있는지 확인
void get_square() {
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (map[i][j] == 1 && map[i + 1][j] == 1 &&
map[i][j + 1] == 1 && map[i + 1][j + 1] == 1)
answer++;
}
}
}
void dragon_curv(int x, int y, int d, int g, int depth, vector<int>& v) {
// 처음 정한 세대까지 그렸을 때 종료
if (g + 1 == depth) {
return;
}
// 새로운 커브를 큐에 역순으로 저장
// 방향은 90도 회전한 값으로 +1해줌
queue<int> q;
if (depth != 0) {
for (int i = v.size() - 1; i >= 0; i--) {
q.push((v[i] + 4 + 1) % 4);
}
}
// 처음에는 그냥 방향값을 넣어준다.
else q.push(d);
int nx = x; int ny = y;
while (!q.empty()) {
// 큐에 있는 값으로 이동을 해주면서 map에 표시
// 다음 세대에 현재까지의 정보가 필요하므로
// vector에 담아 다음 세대에 전달
int direction = q.front();
v.push_back(direction);
q.pop();
nx += dir[direction][0];
ny += dir[direction][1];
map[ny][nx] = 1;
}
dragon_curv(nx, ny, d, g, depth + 1, v);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x, y, d, g;
vector<int> v;
cin >> x >> y >> d >> g;
map[y][x] = 1;
dragon_curv(x, y, d, g, 0, v);
}
get_square();
cout << answer;
}
Reference
この問題について([伯俊]15685号龍曲線(C++、三星機出)), 我々は、より多くの情報をここで見つけました https://velog.io/@khc41/백준-15685번-드래곤-커브-C-삼성-기출テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol