AT_abc232_h [ABC232H] King's Tour

题目描述

有一个纵横为 $H \times W$ 的国际象棋棋盘和 $1$ 个国王棋子。
棋盘上的格子中，从上往下第 $i$ 行（$1 \leq i \leq H$）、从左往右第 $j$ 列（$1 \leq j \leq W$）的格子记作 $(i, j)$。
国王可以从当前位置移动到周围 $1$ 格内的任意格子。更严格地说，只有当棋盘上的两个格子 $(i, j)$ 和 $(k, l)$ 满足 $\max(|i-k|, |j-l|) = 1$ 时，才能将国王从 $(i, j)$ 移动到 $(k, l)$。

我们将满足以下条件的国王移动过程称为一次“巡游”：

• 开始时，将国王放在 $(1, 1)$。之后，国王恰好每个格子都访问一次。

例如，当 $H = 2, W = 3$ 时，按照 $(1,1) \to (1,2) \to (1,3) \to (2,3) \to (2,2) \to (2,1)$ 的顺序移动国王，就满足条件。

现在给定棋盘上 $(1,1)$ 以外的一个格子 $(a, b)$。请构造并输出一种巡游方案，使得国王最后停在 $(a, b)$。在本题的约束下，解一定存在。

输入格式

输入从标准输入按以下格式给出。

$H$ $W$ $a$ $b$

输出格式

请输出 $HW$ 行。第 $i$ 行输出国王第 $i$ 次停留的格子 $(h_i, w_i)$，格式如下：

$h_i$ $w_i$

其中，第 $1$ 行必须输出 $(1, 1)$，第 $HW$ 行必须输出 $(a, b)$。

输入输出样例 #1

输入 #1

3 2 3 2

输出 #1

1 1
1 2
2 1
2 2
3 1
3 2

说明/提示

约束

• $2 \leq H \leq 100$
• $2 \leq W \leq 100$
• $1 \leq a \leq H$
• $1 \leq b \leq W$
• $(a, b) \neq (1, 1)$
• 所有输入均为整数。

样例解释 1

国王可以按 $(1,1) \to (1,2) \to (2,1) \to (2,2) \to (3,1) \to (3,2)$ 的顺序移动，这样确实以 $(3,2)$ 作为终点的巡游。满足条件的巡游方案还有其他几种，例如以下三种移动方式：

• $(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)$

由 ChatGPT 4.1 翻译