P1913螺旋矩陣
Accepted
标簽:
NOIP普及組2014
描述
一個 n 行 n 列的螺旋矩陣可由如下方法生成:
從矩陣的左上角(第 1 行第 1 列)出發,初始時向右移動;如果前方是未曾經過的格子, 則繼續前進,否則右轉;重複上述操作直至經過矩陣中所有格子。根據經過順序,在格子中 依次填入 1, 2, 3, ... , n2,便構成了一個螺旋矩陣。
下圖是一個 n = 4 時的螺旋矩陣。
11211102131693141584567
現給出矩陣大小 n 以及 i 和 j,請你求出該矩陣中第 i 行第 j 列的數是多少。
格式
輸入格式
輸入共一行,包含三個整數 n,i,j,每兩個整數之間用一個空格隔開,分别表示矩陣大小、待求的數所在的行号和列号。
輸出格式
輸出共一行,包含一個整數,表示相應矩陣中第 i 行第 j 列的數。
樣例1
樣例輸入1[複制]
4 2 3
樣例輸出1[複制]
14
限制
對于 50%的資料,1 ≤ n ≤ 100;
對于 100%的資料,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n。
來源
NOIP2014 普及組
解析:将整個矩陣看成 “回” 形狀的分層結構,然後進行去層處理,使得要求得(i,j)處于最外層,然後再分情況讨論。
1.等差數列求和。
最外面的一層共有數: 4*n-4
第二層共有數: 4*n-4 -8
.. ....
假設(i,j)外共有 x 層,則外層所有的數為:ans=4*n*x-4*x*x。
2.将外層全部剝離後,此時(i,j)就處于矩陣的最外層,如下陰影部分所示:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cGcq5CN0cjN0QGM0YjMjRWN0EzMzYzXyMTNyQTM2IzLclDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.jpg)
(圖可能有點醜,将就着看吧)
接下來就是分情況讨論當(i,j)處于矩陣最外層時,位于(i,j)的數是多少。
代碼:
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n,i,j,k,x,ans;
scanf("%d%d%d",&n,&i,&j);
x=min(i-1,n-i);
x=min(x,j-1);
x=min(x,n-j);
ans=4*n*x-4*x*x;
if(i-x==1)ans+=j-x;
else
if(i+x==n)ans+=3*n-5*x-1-j;
else
if(j-x==1)ans+=4*n-7*x-2-i;
else ans+=n-3*x+i-1;
printf("%d\n",ans);
return 0;
}