[NOIP 2014 普及组] 螺旋矩阵

知识点

矩阵、分层计数、分类讨论

解题思路

令d为位置到四条边的最短距离，则它在第d层方环，剩余边长w=n-2d。外面已填n²-w²个数。把坐标减d后，按上边、右边、下边、左边的顺时针顺序计算本环偏移，再加外层已填数。

正确性说明

每剥去一层，内部剩一个边长减少2的正方形，外层已填数因此为原面积减内部面积。当前层沿四边依次填数，分段偏移精确等于当前位置在该顺序中的序号。四种情况覆盖方环，中心单格由上边情况处理。

易错点

同一角点只归入一个分支；奇数n中心边长为1；使用long long计算平方；不能按n²构造矩阵。

复杂度

时间与额外空间均O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long n,i,j;cin>>n>>i>>j;long long d=min({i-1,j-1,n-i,n-j}),w=n-2*d,base=n*n-w*w;i-=d;j-=d;long long off;if(i==1)off=j;else if(j==w)off=w+i-1;else if(i==w)off=2*w-1+w-j;else off=3*w-2+w-i;cout<<base+off<<'\n';}