문제 링크 : https://www.acmicpc.net/problem/1331
문제
나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다.
영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.
입력
36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
- 두 지점에 대한 x와 y의 좌표 차이가 각각 2,1 또는 1,2면 나이트의 움직임과 같다.
- 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있어야 하기 때문에, 시작점과 끝점이 나이트의 움직임인지 검사한다.
- 모든 지점 $p$에 대해 반복하며, $p$와 그 다음 지점 $p+1$ 간의 움직임을 검사하고, 이미 방문한 지점을 또 방문하는지 검사한다.
- 모든 검사 조건을 통과하면 Valid이다.
소스 코드
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
45
46
47
48
|
#include <bits/stdc++.h>
using namespace std;
typedef struct pos {
int r, c;
} pos;
bool check[6][6];
vector<pos> v(36);
bool is_knight_move(pos a, pos b) {
bool ret = false;
int dy = abs(a.r - b.r);
int dx = abs(a.c - b.c);
if (dy == 2 && dx == 1) ret = true;
if (dy == 1 && dx == 2) ret = true;
return ret;
}
string solve() {
if (!is_knight_move(v.front(), v.back())) return "Invalid";
pos post = {-1, -1};
for (pos &now : v) {
bool &visit = check[now.r][now.c];
if (visit) return "Invalid";
else visit = true;
if (post.r != -1 && !is_knight_move(now, post))
return "Invalid";
post = now;
}
return "Valid";
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
for (pos &p : v) {
string s;
cin >> s;
p = {s[0] - 'A', s[1] - '1'};
}
cout << solve();
return 0;
}
|
