CodeForces-1179B Tolik and His Uncle

Table of Contents

CodeForces-1179B Tolik and His Uncle #

题目大意 #

有一个 $n\times m$ 的矩阵 (下标从 $1$ 开始). 从 $(x, y)$ 可以使用方向向量 $(dx, dy)$ 到达 $(x + dx, y + dy)$ . 从 $(1, 1)$ 出发, 遍历所有格点, 同时要求方向向量不能重复. 如果存在这样的走法, 输出点的顺序; 否则输出 $-1$ .

Solution 1 #

从 $1\times m$ 的情况入手, 可以发现行走路径可以是 $(1, 1)\rightarrow (1, m)\rightarrow (1, 2)\rightarrow (1, m - 1)\rightarrow …$ . 推广到 $n\times m$ , 按照 $(1, 1)\rightarrow (n, m)\rightarrow (1, 2)\rightarrow (n, m - 1)\rightarrow …\rightarrow (1,m)\rightarrow (n, 1)\rightarrow (2, m)\rightarrow…$ . 对于 $n$ 为奇数的情况, 最后再在 $\lfloor \frac{n + 1}{2}\rfloor$ 行内部重复 $1\times m$ 的走法即可. 代码如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (n & 1) {
        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 + 1 - i, m + 1 - j);
            }
        }
        for (int j = 1; j <= m; j++) {
            if (j & 1) {
                printf("%d %d\n", n / 2 + 1, 1 + j / 2);
            }
            else {
                printf("%d %d\n", n / 2 + 1, m + 1 - j / 2);
            }
        }
    }
    else {
        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 + 1 - i, m + 1 - j);
            }
        }
    }
    return 0;
}