B3738 [信息与未来 2018] 素数方阵

· · 题解

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

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

为了便于模拟填入素数的过程，我们可以先把前 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;
}

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