P2239螺旋矩阵题解

cwxcplh · 2023-11-11 22:32:03 · 个人记录

由于本人太激动，写下了这篇题解（尽管本人知道不会过）。

传送门

首先通过数据就可以知道：这题绝对不用 O ( n ^ {2} ) 的算法，甚至于数组最多也是一维数组。

通过题目我们可以知道，这个方阵有规律，但是很难找。

经过本蒟蒻的深思熟虑，决定：查看题解（本蒟蒻也很无奈 qwq ）。

但是大佬们太牛叉了（看不懂），于是，我决定自己打一个不同思路的代码。

首先，我们很容易发现：每一个方阵的最后一个数都是 n ^ {2} ，但是这个数具体位于哪呢？这就要分奇偶讨论了

当 n 为奇数时

很明显， n ^ {2} 这个数在正中心，也就是 (n / 2 + 1) 行 (n / 2 + 1) 列（ i , j 分别从 1 开始）

接着，我们要开始找这些数从 n ^ {2} 开始的倒过来排列规则了。从下图中不难发现，奇数的排列就是按照“左下右上”的顺序排列的，四个一循环。

是不是有点明白了？我们继续往下走：我们又发现了一个新的问题：这个数每次经过的数的数量不一样啊？就像 25 到 24 只有一个数，但 19 到 16 却有三个数。

针对这个问题，我们再次发现了规律：每转两个弯，经过的数就多一个。

由于不能用二维数组，我们可以通过坐标计算：当到达了行、列都是所找目标的行、列是，就可以直接输出这个数。

代码如下：

if(n%2==1)
{
    i=j=n/2+1;//行列从中间开始
    ans=n*n;// ans 计数
    while(i!=x||j!=y)//未到达目标点
    {
        if(a%4==0)//第一次转折
        {
            t++;//更新经过的数
            while(k!=t)//一步一步判断
            {
                ans--;
                j--;//往左走
                if(i==x&&j==y)//到达目标点
                {
                    cout<<ans;//直接输出
                    return 0;//程序的终点：一切的沉默
                }
                k++;
            }
            k=0;//还未到达终点！！！
            a++;//新的一轮转折
        }
        else if(a%4==1)//同上，只不过少了更新经过的数
        {
            while(k!=t)
            {
                ans--;
                i++;
                if(i==x&&j==y)
                {
                    cout<<ans;
                    return 0;
                }
                k++;
            }
            k=0;
            a++;
        }
        else if(a%4==2)//同第一组
        {
            t++;
            while(k!=t)
            {
                ans--;
                j++;
                if(i==x&&j==y)
                {
                    cout<<ans;
                    return 0;
                }
                k++;
            }
            k=0;
            a++;
        }
        else if(a%4==3)同第二组
        {
            while(k!=t)
            {
                ans--;
                i--;
                if(i==x&&j==y)
                {
                    cout<<ans;
                    return 0;
                }
                k++;
            }
            k=0;
            a++;
        }
    }
    cout<<ans;
}

当 n 为偶数时

同样，先画个图：

这次的 n ^ {2} 在第 3 行第 2 列，明显感觉是