#abc232h. H - King's Tour
H - King's Tour
Score : points
问题描述
我们有一个 的棋盘,其中包含 行和 列,以及一枚国王棋子。
令 表示从上到下的第 行()和从左到右的第 列()的方格。
国王可以在任何方向上移动一格。正式地,位于 的国王可以移动到 当且仅当 。
tour 是在 棋盘上移动国王的过程,具体如下:
- 首先将国王放在 上。然后,移动国王使其恰好每个方格走过一次。
例如,当 时,路径 $(1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1)$ 是一个有效的 tour。
现在给出棋盘上除 以外的一个方格坐标 ,请构造一条以 结束的 tour,并将其打印出来。可以证明,在本题的约束条件下总是存在解决方案。
以上为通义千问 qwen-max 翻译,仅供参考。
Problem Statement
We have an chessboard with rows and columns, and a king.
Let denote the square at the -th row from the top and -th column from the left .
The king can move one square in any direction. Formally, the king on can move to if and only if .
A tour is the process of moving the king on the chessboard as follows.
- Start by putting the king on . Then, move the king to put it on each square exactly once.
For example, when , going $(1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1)$ is a valid tour.
You are given a square other than . Construct a tour ending on and print it. It can be proved that a solution always exists under the Constraints of this problem.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain the -th square the king is put on, in the following format:
Here, note that the -st line should contain , and the -th line should contain .
Sample Input 1
3 2 3 2
Sample Output 1
1 1
1 2
2 1
2 2
3 1
3 2
The king goes $(1, 1) \to (1, 2) \to (2, 1) \to (2, 2)\to (3, 1) \to (3, 2)$, which is indeed a tour ending on .
There are some other valid tours, three of which are listed below.
- $(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2)$
- $(1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to (3, 1) \to (3, 2)$
- $(1, 1) \to (2, 2) \to (1, 2) \to (2, 1) \to (3, 1) \to (3, 2)$
update @ 2024/3/10 10:08:10