문제 링크: https://www.acmicpc.net/problem/17370
수열을 만들어보려고 했는데 도저히 규칙을 못찾아서(OEIS에도 없음) 풀이 검색을 해봤습니다. 검색해보니 그냥 브루트포스였습니다
하긴 2^22이면 대충 400만이니 다 해볼 수 있습니다
백트래킹을 하다가 이미 방문한 점이면서 이동 횟수가 n번인 경우만 카운트를 해줍니다.
이때 방문했던 점들을 저장하는 방법은 배열로 해도 되고 map 써도 되는데 좌표가 음수가 될 수 있어서 귀찮으니 그냥 map으로 해줍시다
6방향의 좌표는 정수로 계산해줍시다.
#include <bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> visited;
const int dy[] = {2, 1, -1, -2, -1, 1};
const int dx[] = {0, 1, 1, 0, -1, -1};
int cnt;
void backtrack(int y, int x, int dir, int to_move) {
if (to_move == 0) {
if (visited.find({ y,x }) != visited.end())
++cnt;
return;
}
else if (visited.find({ y,x }) != visited.end())
return;
visited[{y, x}] = true;
int dir_right = (dir + 1) % 6;
int dir_left = (dir + 5) % 6;
backtrack(y+dy[dir_right], x+dx[dir_right], dir_right, to_move-1);
backtrack(y+dy[dir_left], x+dx[dir_left], dir_left, to_move-1);
visited.erase({ y,x });
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
visited[{0, 0}] = true;
backtrack(2, 0, 0, n);
cout << cnt << '\n';
return 0;
}
반응형
'Online Judge > 백준' 카테고리의 다른 글
[백준][C++] 1753: 최단경로 (0) | 2020.07.20 |
---|---|
[백준][C++] 1269: 대칭 차집합 (0) | 2020.07.19 |
[백준][C++] 18917: 수열과 쿼리 38 (0) | 2020.07.18 |
[백준][C++] 1072: 게임 (0) | 2020.07.18 |
[백준][C++] 1051: 숫자 정사각형 (0) | 2020.07.17 |