#abc232h. H - King's Tour

H - King's Tour

Score : 600600 points

问题描述

我们有一个 H×WH \times W 的棋盘,其中包含 HH 行和 WW 列,以及一枚国王棋子。
(i,j)(i, j) 表示从上到下的第 ii 行(1iH1 \leq i \leq H)和从左到右的第 jj 列(1jW1 \leq j \leq W)的方格。
国王可以在任何方向上移动一格。正式地,位于 (i,j)(i,j) 的国王可以移动到 (k,l)(k,l) 当且仅当 max(ik,jl)=1\max(|i-k|,|j-l|) = 1

tour 是在 H×WH \times W 棋盘上移动国王的过程,具体如下:

  • 首先将国王放在 (1,1)(1, 1) 上。然后,移动国王使其恰好每个方格走过一次。

例如,当 H=2,W=3H = 2, W = 3 时,路径 $(1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1)$ 是一个有效的 tour。

现在给出棋盘上除 (1,1)(1, 1) 以外的一个方格坐标 (a,b)(a, b),请构造一条以 (a,b)(a,b) 结束的 tour,并将其打印出来。可以证明,在本题的约束条件下总是存在解决方案。

以上为通义千问 qwen-max 翻译,仅供参考。

Problem Statement

We have an H×WH \times W chessboard with HH rows and WW columns, and a king.
Let (i,j)(i, j) denote the square at the ii-th row from the top (1iH)(1 \leq i \leq H) and jj-th column from the left (1jW)(1 \leq j \leq W).
The king can move one square in any direction. Formally, the king on (i,j)(i,j) can move to (k,l)(k,l) if and only if max(ik,jl)=1\max(|i-k|,|j-l|) = 1.

A tour is the process of moving the king on the H×WH \times W chessboard as follows.

  • Start by putting the king on (1,1)(1, 1). Then, move the king to put it on each square exactly once.

For example, when H=2,W=3H = 2, W = 3, 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 (a,b)(a, b) other than (1,1)(1, 1). Construct a tour ending on (a,b)(a,b) and print it. It can be proved that a solution always exists under the Constraints of this problem.

Constraints

  • 2H1002 \leq H \leq 100
  • 2W1002 \leq W \leq 100
  • 1aH1 \leq a \leq H
  • 1bW1 \leq b \leq W
  • (a,b)(1,1)(a, b) \neq (1, 1)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

HH WW aa bb

Output

Print HWHW lines. The ii-th line should contain the ii-th square (hi,wi)(h_i, w_i) the king is put on, in the following format:

hih_i wiw_i

Here, note that the 11-st line should contain (1,1)(1, 1), and the HWHW-th line should contain (a,b)(a, b).

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 (3,2)(3, 2).
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