1967:【14NOIP普及组】螺旋矩阵


时间限制: 1000 ms         内存限制: 131072 KB
提交数:6478    通过数: 2285

【题目描述】

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

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

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

1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

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

【输入】

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

【输出】

输出共一行,包含一个整数,表示相应矩阵中第 i 行第 j 列的数。

【输入样例】

4 2 3

【输出样例】

14

【提示】

【数据说明】

对于 50%的数据,1  ≤  n  ≤  100;

对于 100%的数据,1  ≤  n  ≤  30,000,1  ≤  i  ≤  n,1  ≤  j  ≤  n。

#include<iostream>
#include<cmath>
using namespace std;
//long long a[15000][15000];
int main(){
    int n,x,y,s=1,ans;
    long long st=1,minn=900000000;
    cin>>n>>x>>y;
    if(minn>x)minn=x;
    if(minn>y)minn=y;
    if(minn>(n-x+1))minn=n-x+1;
    if(minn>(n-y+1))minn=n-y+1;

    int l =n;
    for(int i=1;i<minn;i++){

        st=st+4*l-4;
        l-=2;

    }
    if(x==minn)  cout<<st+y-minn;
    else if(y==n-minn+1)cout<<st+l+x-minn-1;
    else if(x==n-minn+1)cout<<st+l+l-2+(n-minn+1)-y;
    else if(y==minn)cout<<st+l+l+l-3+(n-minn+1)-x;
    return 0;
}

Logo

集算法之大成!助力oier实现梦想!

更多推荐