시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 8212 | 2623 | 2237 | 33.558% |
나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다.
영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.
36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.
첫째 줄에 문제의 정답을 출력한다.
A1 B3 A5 C6 E5 F3 D2 F1 E3 F5 D4 B5 A3 B1 C3 A2 C1 E2 F4 E6 C5 A6 B4 D5 F6 E4 D6 C4 B6 A4 B2 D1 F2 D3 E1 C2
Valid
A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3 A1 C2 E3 F5 D4 B3
Invalid
D4 F5 D6 B5 A3 B1 D2 F1 E3 D1 F2 E4 F6 D5 B6 A4 B2 C4 A5 C6 E5 F3 E1 C2 A1 B3 C5 E6 F4 E2 C3 A2 C1 D3 B4 A6
Invalid
D4 F5 D6 B5 A3 B1 D2 F1 E3 D1 F2 E4 F6 D5 B6 A4 B2 C4 A5 C6 E5 F3 E1 C2 A1 B3 C5 A6 B4 A2 C3 E2 C1 D3 F4 E6
Valid
C5 D3 F2 D1 B2 A4 B6 D5 C3 E4 F6 B3 A1 C2 E1 F3 E5 C6 A5 C4 A3 B1 D2 F1 E3 F5 D6 B5 D4 E6 F4 E2 C1 A2 B4 A6
Invalid