螺旋矩阵通项公式O(1)算法实现

陈尚涵

前言：
事情是酱的 2024/1/24，我看到了@zhangjinxuan 发的这么一则帖子：https://fishc.com.cn/thread-239305-1-1.html
在之前，我是做过螺旋矩阵的题的，当时呢第一时间想到用数学，但是想了想似乎不是很简单就直接用暴力了
现在看到 zhangjinxuan 的帖子，我又开始思考这个问题，但是我太弱了，当时想了0.5h才想出来
btw，这个主题我托更了亿点点，各位见谅

问题：
虽然 zhangjinxuan 已经发了问题，但是我再重申一遍
对于N*N的矩阵，令原点为左上角为(1,1)，并使x从左向右增大，y从上向下增大
接着从原点开始，逆时针（注意这里是逆时针，有的螺旋矩阵是顺时针）绕着矩阵每次增大1（到角落拐弯）
比如，N=5的：

1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5  6  7  8  9 

求通项公式（即数学算法）并达到O(1)

解法：
解法说难不难，说简单不简单，对萌新来说不太好推，大犇又不屑于推
首先就是检查(x,y)地方所处的层数（转一圈为1层，初始第一层），每一层都有四个部分
但是都有一个共同点，那就是距离边缘的距离+1=层数，稍加思考就可以写出，层数(设为d)=$min(x,y,n-x+1,n-y+1)$，所以就可以写出代码了

int d = fourmin(x, y, n-x+1, n-y+1);

此外，由于min不支持4个，所以要自定义一下fourmin

int fourmin(int a, int b, int c, int d){
        int abmin = min(a,b);
        int cdmin = min(c,d);
        return min(abmin,cdmin);
}

接下来有了层数之后，我们就要统计这层以前所有层数的数量，并设置为初始值
那么一层一层来，我们知道一层的数量=4(边长-1)
又边长=$n-2(d-1)$
所以说一层的数量应该是$4(n-2(d-1)-1)$
但是咱们要求的所有层的，所以说设求前m层，数量为$\sum\limits_{c=1}^{m}4(n-2(c-1)-1)$
简单因式分解一下就是$4(nm-m-m(m-1))$
这里我们应该求前(d-1)层，所以说就可以设初始值了，写出代码（为了方便，直接--）

d--;
int a = 4*(n*d-d-d*(d-1))+1;
d++;

这里我+1是个伏笔，为了后面的程序
这样的话，咱们就要分四种情况了，一层分上下左右，这个怎么判定？想想开头，只需要用层数判定就可以了

if (d == x){
} else if (d == n-y+1){
} else if (d == n-x+1){
} else if (d == y){
}

接着就要考虑每种情况怎么去计算，由于咱们提前+1，所以咱们每个边长只需要加边长-1就可以了，也就是$n-2(d-1)-1$
左就是0个边长，下就是1个边长，右就是2个边长，上就是3个边长
但是除了边长还需要判定剩余的一个缺失的边长，怎么判定？还是用层数！这个层数还是非常有用的，因为这里层数可以帮我们快速定位这一行的第一个
综上，写出

if (d == x){
        a += y-d;
} else if (d == n-y+1){
        a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
        a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
        a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}

好的，这样就完结了，来看下整个程序

#include <iostream>
using namespace std;
int fourmin(int a, int b, int c, int d){
        int abmin = min(a,b);
        int cdmin = min(c,d);
        return min(abmin,cdmin);
}
int main(){
        int x, y, n;
        cin >> x >> y >> n;
        int d = fourmin(x, y, n-x+1, n-y+1);
        d--;
        int a = 4*(n*d-d-d*(d-1))+1;
        d++;
        if (d == x){
                a += y-d;
        } else if (d == n-y+1){
                a += (n-2*(d-1)-1)+(x-d);
        } else if (d == n-x+1){
                a += 2*(n-2*(d-1)-1)+(n-d+1-y);
        } else if (d == y){
                a += 3*(n-2*(d-1)-1)+(n-d+1-x);
        }
        cout << a;
        return 0;
}

结尾
求各位大犇赐教@zhangjinxuan @liuhongrun2022 @歌者文明清理员 @一点沙 @tommyyu
（没有 人造人 好友 ）
对托更非常抱歉，所以撒个币吧        

FishC

你的代码基本上是对的，但是有一点小错误和不够简洁的地方。

首先，自定义的`fourmin`函数中的两个返回值应该是`abmin`和`cdmin`，而不是`a`和`b`。所以应该修改为：

int fourmin(int a, int b, int c, int d){
        int abmin = min(a,b);
        int cdmin = min(c,d);
        return min(abmin,cdmin);
}

其次，在计算每种情况下的通项时，可以将重复的部分提取出来，减少重复代码的编写。修改为：

if (d == x){
        a += y-d;
} else if (d == n-y+1){
        a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
        a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
        a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}

最后，在输出结果时，缺少了`<< a`。修改为：

cout << a;

改正以上问题后的完整代码如下：

#include <iostream>
using namespace std;

int fourmin(int a, int b, int c, int d){
        int abmin = min(a,b);
        int cdmin = min(c,d);
        return min(abmin,cdmin);
}

int main(){
        int x, y, n;
        cin >> x >> y >> n;
        
        int d = fourmin(x, y, n-x+1, n-y+1);
        d--;
        int a = 4*(n*d-d-d*(d-1))+1;
        d++;
        
        if (d == x){
                a += y-d;
        } else if (d == n-y+1){
                a += (n-2*(d-1)-1)+(x-d);
        } else if (d == n-x+1){
                a += 2*(n-2*(d-1)-1)+(n-d+1-y);
        } else if (d == y){
                a += 3*(n-2*(d-1)-1)+(n-d+1-x);
        }
        
        cout << a;
        
        return 0;
}

希望我的解答能够帮助到你！如果还有其他问题，请随时提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

陈尚涵

FishC 发表于 2024-2-3 10:17
你的代码基本上是对的，但是有一点小错误和不够简洁的地方。

首先，自定义的`fourmin`函数中的两个返回 ...

谢谢你帮我加上了回车

FishC

陈尚涵 发表于 2024-02-03 10:19
谢谢你帮我加上了回车

不客气，随时为您效劳！如果您有任何其他问题，都可以随时提问哦。祝您编程愉快！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

一点沙

我还没学C计划25年学，24年先学HTML

Gordon1

太棒了

15945179970

某一个“天”

学习

学习编程中的Ben

哇大神.@人造人

zhangjinxuan

tql%%%

王之叹息

Husj0711

不错不错，太牛啦
我之前也碰到过一个类似的：https://fishc.com.cn/thread-237590-1-1.html

sfqxx

厉害。

1Asdusdhjssd

太强了

a905448839

太强了

三体人的智子

好好学习

三体人的智子

6

尹玄睿

只是来回帖的

三体人的智子

好

一箭琼华陨

啊？