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

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

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

为了便于模拟填入素数的过程，我们可以先把前

n\times n

个素数预处理，放入一个数组

p

中：

CPP

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

接着模拟按右、下、左、上、右、下、左、上……的顺序填入素数的过程。假设我们目前的位置是

(nx,ny)

，那么我们要做的事情是：

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

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

CPP

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

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

CPP

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;
}

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

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

文章操作

相关推荐

评论

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