기사의 여행
골드 I의견: 0
체스의 기사(나이트)는 한 번에 한 방향으로 두 칸, 그와 수직인 방향으로 한 칸 이동한다. 즉 어떤 칸에서 기사가 갈 수 있는 칸은 아래 그림처럼 최대 \(8\)곳이며, 이동 모양이 알파벳 L을 닮았다.
\(N \times M\) 크기의 격자 모양 들판이 있다. 위에서부터 \(i\)번째 행, 왼쪽에서부터 \(j\)번째 열에 있는 칸을 \((i, j)\)로 나타낸다. 한 마리의 기사가 칸 \((r, c)\)에서 출발하여, 나이트 이동만을 사용해 들판의 모든 칸을 정확히 한 번씩 방문하려고 한다. 이렇게 모든 칸을 한 번씩 밟고 지나가는 경로를 열린 나이트 투어라고 부른다.
\((r, c)\)에서 출발하는 열린 나이트 투어가 존재하는지 판별하고, 존재한다면 그러한 경로를 하나 구하는 프로그램을 작성하시오. 같은 칸을 두 번 밟아서는 안 된다.
- \(1 \le N, M \le 200\)
- \(1 \le r \le N\), \(1 \le c \le M\)
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 들판의 행의 수 \(N\)과 열의 수 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 기사가 출발하는 칸의 행 번호 \(r\)과 열 번호 \(c\)가 공백으로 구분되어 주어진다.
\((r, c)\)에서 출발하여 모든 칸을 정확히 한 번씩 방문하는 열린 나이트 투어가 존재하면, \(N\)개의 줄에 각 줄마다 \(M\)개의 정수를 공백으로 구분하여 출력한다. \(i\)번째 줄의 \(j\)번째 정수는 기사가 칸 \((i, j)\)를 몇 번째로 방문하는지를 나타내는 \(1\) 이상 \(N \cdot M\) 이하의 정수여야 한다.
즉, 출발 칸 \((r, c)\)에 적히는 수는 반드시 \(1\)이어야 하고, \(1\)부터 \(N \cdot M\)까지의 각 수가 정확히 한 번씩 나타나야 하며, 수 \(k\)가 적힌 칸과 수 \(k+1\)이 적힌 칸은 서로 나이트 이동으로 오갈 수 있어야 한다.
그러한 경로가 존재하지 않으면 \(-1\)만을 출력한다.
가능한 경로가 여러 개인 경우 그중 아무거나 하나만 출력하면 된다. (스페셜 저지)
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(1 \le N, M \le 8\) |
Subtask 2 | 40점 | \(1 \le N, M \le 50\) |
Subtask 3 | 30점 | 추가 제한이 없다. |
5 5
1 11 20 9 14 3
10 15 2 19 24
21 8 23 4 13
16 11 6 25 18
7 22 17 12 5출발 칸인 \((1, 1)\)에 \(1\)이 적혀 있고, \(1\)부터 \(25\)까지의 수가 각각 한 번씩 나타난다. 또한 연속한 두 수가 적힌 칸끼리는 항상 나이트 이동으로 이어져 있으므로, 이는 올바른 열린 나이트 투어이다. 이 문제는 스페셜 저지이므로 조건을 만족하는 다른 경로를 출력해도 정답으로 인정된다.
3 4
1 11 4 7 10
8 11 2 5
3 6 9 12\(3 \times 4\) 들판의 왼쪽 위 칸에서 출발하는 열린 나이트 투어의 한 예이다. 기사는 \(1 \to 2 \to \cdots \to 12\)의 순서로 모든 칸을 한 번씩 방문한다.
4 4
1 1-1\(4 \times 4\) 들판에서는 어느 칸에서 출발하더라도 모든 칸을 한 번씩 방문하는 열린 나이트 투어가 존재하지 않는다. 따라서 \(-1\)을 출력한다.
riseoj 작성
출처 Original
평가 및 의견
기사의 여행
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
기사의 여행