Traversal

[morris821028]

Problem Description

The task is to start from a given cell, traverse every cell of an $n$ by $m$ matrix in a loop without duplication. For example, if $n = 2$ and $m = 2$ and we start from $(1, 0)$, then we can go from $(1, 0)$, to $(1, 1)$, to $(0, 1)$, to $(1, 1)$, then back to $(1, 0)$. For simplicity we assume that $m$ is always an even number.

Subtasks

• 5pt. $m = 2$ and $n = 2$.
• 10pt. $m = 2$ and $n \geq 2$.
• 10pt. $m = 4$ and $n \geq 2$.
• 20pt. $m = 6$ and $n \geq 2$.
• 55pt. $m$ is no more than 500, and $2 \leq n \leq 512$.

Hints

• For any matrix of even number of columns, we can start from $(0, 0)$, go up to $(0, m - 1)$, then go right to $(n - 1, m - 1)$, then do a snake-like zig-zag traversal back to $(1, 0)$, then go back to $(0, 0)$.

p10077-sample input 2

p10077 generic solution

- Since we can go through all cells in a loop, then we only need to identify the given cell in this loop, then print all cells along the way in order. ## Input Format

There are many cases in one input file, please read it until EOF.

There are four numbers in one case.

The first two numbers means the size of the $n$ by $m$ matrix. The first number is $n$. The second number is $m$.

The last two numbers means the cell that you start from.

Sample Input 1

2 2 0 0

Sample Output 1

0 0
0 1
1 1
1 0
0 0

Sample Input 2

3 4 1 2

Sample Output 2

1 2
2 2
2 3
1 3
0 3
0 2
0 1
0 0
1 0
2 0
2 1
1 1
1 2

Sample Input 3

2 2 0 0
3 4 1 2

Sample Output 3

0 0
0 1
1 1
1 0
0 0
1 2
2 2
2 3
1 3
0 3
0 2
0 1
0 0
1 0
2 0
2 1
1 1
1 2