「Codeforces 1180D」Tolik and His Uncle

题目链接: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;
}

发表评论