【NOIP2014】螺旋矩阵

· · 个人记录

题目描述：--->螺旋矩阵

看到题,很明显,如果直接模拟的话,复杂度为O(n^2)O(n 2 )过不去.(这个复杂度应该不正确,我不会分析的啊 qwq.

因此我们需要一个比较厉害的方法解决这个题

前置知识

我们手写一些矩阵,发现我们填的数是会分层的 ！

同种颜色为一层

分层这个东西的话,我也不能具体解释,你可以认为是一圈一圈地填数.

蒟蒻分析

打表，找规律

我们可以手写一个程序

模拟一下这个过程

例如这个程序

(话说,打个表我想了半小时? qwq 一定是我太垃圾了）

下面的变量cengceng的话,是因为构造出来的矩阵会分层。

void get(int n)
{
    int cnt=0,x=1,y=1;
    for(R int ceng=1;ceng<=(n+1)/2;ceng++)
    {
        while(y<=n-ceng+1)
            res[x][y++]=++cnt;x++;y--;
        while(x<=n-ceng+1)
            res[x++][y]=++cnt;x--;y--;
        while(y>=ceng)
            res[x][y--]=++cnt;y++;x--;
        while(x>ceng)
            res[x--][y]=++cnt;x++;y++;
    }
    print();
}

打出来5*5的表是这样的 qwq

开始找规律

  1. 第i行第j列对应的数就是j
  2. 第n列第i行对应的为n+i-1
  3. 第n行第j列对应的数为3*n-j-1
  4. 再度填回第1列,第i行我们发现得到的对应数为4*n-i-2

上面四点是最容易发现的规律,也是我们继续求解的关键

如何填充里层的数

总的来说,每一层共可以*填充4n-4个数**

然后考虑搞事。

我们将更里层的数减去4*n-4,得到新的里层数据如下.

恍然大悟

我们发现,这样的话,我们又填一次这个矩阵,不过这个矩阵的大小从n变成了n-2

而假设我们之前要查找的数的位置为(4,4)就变成了(3,3)

所以说,当我们求内层的时候,所求原数的位置(x,y)就将变成(x-1,y-1).

而对于那些直接满足上面我们发现的规律的数的话,我们可以直接输出.

所以不必考虑这些数的输出怎么办.

最终我们一定会拆到最里层.

依此类推

我们一直拆下去,每次加上的答案就是4*n-4。

注意:这个n是在变化的.

因此我们可以码出代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;
int n,x,y,ans;
int main()
{
    scanf("%d%d%d",&n,&x,&y);
    here:;
    if(x==1)ans=y+ans;
    else if(y==n)ans=n+x-1+ans;
    else if(x==n)ans=3*n-y-1+ans;
    else if(y==1)ans=4*n-x-2+ans;
    else
    {
        ans+=4*n-4;
        x--;y--;n-=2;
        goto here;
        //达到递归的效果
        //我们的程序运行到这一步会到达上面的here,即再度执行这些if语句 
    }
    printf("%d",ans);
    return 0;
}