洛谷B3738素数方阵

url: https://www.luogu.com.cn/problem/B3738

tag：
模拟，数学

思路：
数据范围比较小，可以用模拟的方式来通过这道题。比较难的部分应该是蛇形填充。这里可以先用一个数组来存放四个前进的方向。之后每次都判断一下前进之后的位置符不符合要求（不越界且当前位置没有被填充过），如果符合要求则前进，然后将数字放进矩阵，否则就换一个方向。

代码：

#include <iostream>
using namespace std;
int n, x, y;
const int N = 22;
int p[410], dp[N][N], d;
int dir[4][2] = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0},
};
bool is_pr(int x)
{
    for (int i = 2; i * i <= x; i ++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    cin >> n >> x >> y;
    int k = 2;
    for (int i = 1; i <= n * n; i ++)
    {
        while (!is_pr(k++));
        p[i] = --k;
        k ++;
    }
    int nx = 0, ny = 0;
    dp[0][0] = p[1];
    for (int i = 2; i <= n * n; i ++)
    {
        int tmpx, tmpy;
        tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        if (tmpx >= n || tmpx < 0 || tmpy >= n || tmpy < 0 || dp[tmpx][tmpy])
        {
            d = (d + 1) % 4;
            tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        }
        nx = tmpx, ny = tmpy;
        dp[nx][ny] = p[i];
    }
    cout << dp[x - 1][y  - 1] << endl;
    return 0;
}