题目链接：Codeforces 1180D

你有一个 $n \times m$ 的网格图，最初你在 $(1, 1)$ 的位置。每次你需要选择一个 $(dx, dy)$，从当前位置 $(x, y)$ 移动到 $(x + dx, y + dy)$ 的位置。显然你不能离开网格，而且你必须将每个格子访问恰好一次（最初的 $(1, 1)$ 被认为是已经访问过了），所使用的 $(dx, dy)$ 还需要保证两两不同。

数据范围：$1 \le n \cdot m \le 10 ^ 6$。

Solution

有一个比较好想的构造方法：反复横跳！

首先遍历第 $1, n$ 行（这些操作的 $dy$ 两两不同）：$(1, 1) \rightarrow (n, m) \rightarrow (1, 2) \rightarrow (n, m - 1) \rightarrow \dots \rightarrow (1, m) \rightarrow (n, 1)$；接下来遍历第 $2, n - 1$ 行，具体方法为直接从 $(n, 1)$ 跳到 $(2, 1)$；如此反复……

时间复杂度：$\mathcal O(nm)$。

Code

#include <cstdio>

int n, m;

int main() {    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n / 2; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%d %d\n", i, j);
            printf("%d %d\n", n - i + 1, m - j + 1);
        }
    }
    if (n & 1) {
        int x = n / 2 + 1;
        for (int i = 1, l = 1, r = m; i <= m; i++) {
            printf("%d %d\n", x, i & 1 ? l++ : r--);
        }
    }
    return 0;
}