♐ CSP_J 组真题
2014年
3. 螺旋矩阵

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1967 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/461/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P2239 (opens in a new tab)

背景知识:

螺旋矩阵可以采用模拟的方式生成。就是顺时针四个方向

第1步、是第 1 行,方向为从左到右,数值+1。当向遇到 边界n 或者 格子已填过数值 时停止
第2步、是第 n 列,方向为从上到下,数值+1。当向遇到 边界n 或者 格子已填过数值 时停止
第3步、是第 n 行,方向为从右到左,数值+1。当向遇到 边界0 或者 格子已填过数值 时停止
第4步、是第 1 列,方向为从下到上,数值+1。当向遇到 边界0 或者 格子已填过数值 时停止

以上四步为一轮。然后开始下一轮,直至数值填满达到 n*n 为止。

本题的第一种常规解法,是先生成螺旋矩阵,然后输出其中的数值。但是题中的n会达到30000,此时开a[n][n]的二位矩阵在空间上会爆,所以这种方法只能拿50分。

代码如下:

先生成矩阵,再输出(50%分数)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int a[maxn][maxn];
int n, i ,j;
int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};
 
void cal() {
    int x = 0, y = 0;
    a[x][y] = 1;
    for (int k = 2; k <= n * n; )
    {
        for(int t = 0; t < 4; t++)
        {
            while (1)
            {
                int nx = x + dx[t], ny = y + dy[t];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny])  break;
 
                a[x = nx][y = ny] = k++;
            }
        }     
    }
}
int main() {
    cin >> n >> i >> j;
    cal();
    cout << a[i-1][j-1];
    return 0;
}