自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:14:44，当前版本为作者最后更新于2025-03-08 13:04:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考察模拟、素数判断。

为了便于模拟填入素数的过程，我们可以先把前 $n\times n$ 个素数预处理，放入一个数组 $p$ 中：

for (int i = 2; num <= n * n; i++) {
    if (isPrime(i)) {
        num++; // 统计当前有 num 个素数
        p[num] = i;
    }
}

接着模拟按右、下、左、上、右、下、左、上……的顺序填入素数的过程。假设我们目前的位置是 $(nx,ny)$，那么我们要做的事情是：

• 将目前的位置填上素数；
• 根据之前的方向，往后续的格子“试探”一步。如果没有问题就继续沿着这个方向走，如果到达了边界/被素数占领了，则转向尝试。

在代码中，你可以定义两个常量方向数组，以便处理拐弯的情况。在本题中，由于保证了移动方向为右下左上，因此方向数组的写法是唯一的：

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

定义了方向数组之后，就可以用下面代码的方式模拟填数的流程：

int nx1 = nx + dx[dir], ny1 = ny + dy[dir];
// 往后续的格子“试探”一步
if (nx1 < 1 || nx1 > n || ny1 < 1 || ny1 > n || a[nx1][ny1]) { // 到达了边界/被素数占领了
    dir = (dir + 1) % 4; // 转向
    nx += dx[dir];
    ny += dy[dir];
} else { // 无事发生
    nx = nx1;
    ny = ny1;
}

这样，我们就通过模拟法高效地解决了这一道题目。