Solution of P13348 「ZYZ 2025」未选择的路

· · 题解

题意

在一个网格图中，要从 (0,0) 到达 (n,n)。只能沿某个方格的对角线移动，并且每个方格至多经过一次。求最多能经过多少方格，并给出一种可行的方案。

解法

根据部分分，可以想到需要按 n 的奇偶分类。

n 为奇数

![图片](https://cdn.luogu.com.cn/upload/image_hosting/4nvenjk1.png) #### $n$ 为偶数 一种想法是只走 $(n-1)^2 + 1$ 个格子，像这样： ![图片](https://cdn.luogu.com.cn/upload/image_hosting/cijx0eth.png) 但是这不是最优解，通过模拟数据或证明可以得出：最多只能走 $(n-1)n$ 个格子。 延续上面的思路，可以得出一种构造方式： ![图片](https://cdn.luogu.com.cn/upload/image_hosting/k28o3nqa.png) 把所有在副对角线（虚线）上的格子全部避开，其他按照“蛇形”走法即可。 观察图片可得：走到副对角线上时，需要按照先前的方向再走一步。 按这种方法实现即可，注意细节。 ### $\mathfrak{Code} 
#include <bits/stdc++.h>

using namespace std;

void calc(int i, int j, int &x, int &y, int &lst) // 计算下一个位置
{
    if (i % 2 == 1 && j % 2 == 1)
    {
        x++;
        y++;
        lst = 0;
    }
    if (i % 2 == 1 && j % 2 == 0)
    {
        x++;
        y--;
        lst = 1;
    }
    if (i % 2 == 0 && j % 2 == 1)
    {
        x--;
        y++;
        lst = 2;
    }
    if (i % 2 == 0 && j % 2 == 0)
    {
        x--;
        y--;
        lst = 3;
    }
}

int dx[4] = {1, 1, -1, -1};
int dy[4] = {1, -1, 1, -1};

int x = 0, y = 0, lst = 0, val = 0; //lst代表上一次的方向，val代表在该行是否已经经过了副对角线。

int main()
{
    int n;

    scanf("%d", &n);

    if (n % 2 == 1) // 奇数
    {
        printf("%d\n", n * n);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                calc(i, j, x, y, lst);
                printf("%d %d\n", x, y);
            }
        }
    }
    else // 偶数
    {
        printf("%d\n", n * (n - 1));
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (x + y == n) // 走到副对角线上时，需要按照先前的方向再走一步。
                {
                    x += dx[lst];
                    y += dy[lst];
                    val ^= 1;
                    printf("%d %d\n", x, y);
                    continue;
                }

                calc(i, j + val, x, y, lst);

                printf("%d %d\n", x, y);
            }

            val = 0;
        }
    }

    return 0;
}