Problem

题目背景

NOIP2014 普及组 T3

题目描述

一个 $n$ 行 $ n$ 列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第 $1$ 行第 $1$ 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 $1, 2, 3, \dots, n^2$，便构成了一个螺旋矩阵。

下图是一个 $n = 4$ 时的螺旋矩阵。

$$\begin{pmatrix}
1 & 2 & 3 & 4 \
12 & 13 & 14 & 5 \
11 & 16 & 15 & 6 \
10 & 9 & 8 & 7 \
\end{pmatrix}$$

现给出矩阵大小 $n$ 以及 $i$ 和 $j$，请你求出该矩阵中第 $i$ 行第 $j$ 列的数是多少。

输入格式

共一行，包含三个整数 $n$, $i$, $j$，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。

输出格式

一个整数，表示相应矩阵中第 $i$ 行第 $j$ 列的数。

样例 #1

样例输入 #1

4 2 3

样例输出 #1

提示

【数据说明】

对于 $50%$ 的数据，$1 \leqslant n \leqslant 100$;

对于 $100%$ 的数据，$1 \leqslant n \leqslant 30,000,1 \leqslant i \leqslant n,1 \leqslant j \leqslant n$。

Solution

1.题目分析

这个题目是一个简单的模拟（这里只是说其中一种做题方案，其实还可以用其他方法）

2.思路分析

~~既然已经说了是模拟，那么就是模拟呗~~

其实，模拟根本就不需要开 30000*30000 的数组。考虑到它是求第i行第j列的数，其实我们可以只针对第j列的数，进行填数模拟，这样时间复杂度就降到了O(N)了。模拟其实也很简单，就是向右绕半圈，向左绕半圈，直到行等于i时跳出就可以了。

另外，如果这样模拟，就会有一个坑点难以想到。有时候，可能绕的这半圈已经变成了一条直线了，这样这第i行的数就可能在这条直线中，则必须加一个特判，加上上一个点到终点的距离，然后就得跳出了。如果不加特判，程序继续运行，模拟便会出错，然后就只有 60 分了……

话不多说，模拟也就是这么一回事了！那么，我们上代码吧！

Code

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main()
{
    int n, x, y;
    cin >> n >> x >> y ;
    int rx = 1, num = y;  // rx为模拟到的行数，num为目前加到的数，也是最终输出的结果
    int up = 1, down = n, zuo = 1, you = n;  // x、y在下一次绕圈时上下左右的边界值（可以理解为将要被蛇形填数的一圈的边界）
    bool fx = true;  // 方向（true往下，false往上）
    while (rx != x)  // 一直模拟到刚好到达
    {
        if (fx)  // 特判
        {
            if (you == y)  // 如果是往下走直线
            {
                num += x - rx;  // 加上最后的数
                break;
            }
        }
        else
        {
            if (zuo == y)  // 如果是向上走直线
            {
                num += rx - x;
                break;
            }
        }
        if (fx) // 普通情况，如果向下走
        {
            num += (you - y + 1) * 2 + down - rx - 2;  // 绕一圈
            rx = down;  // 更新所在的行
            you -- ;  // 右边界往回退一格
            up ++ ;  // 上边界往回退一格
        }
        else // 往上走
        {
            num += (y - zuo + 1) * 2 + rx - up - 2;  // 绕一圈
            rx = up;  // 更新行
            zuo  ++  ;  // 左边界向内
            down -- ;  // 下边界向内
        }
        fx = !fx;  // 方向调转
    }
    cout << num ;
    return 0;
}

~~支持一下吧球球啦！~~

Summary

通过模拟方向来输出，最后再说一句：请勿直接复制题解，需自行理解再重写，tj不是你ac的理由哦！

「题解」 [NOIP2014 普及组] 螺旋矩阵