螺旋矩阵通项公式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. 1 16 15 14 13
   
2. 2 17 24 23 12
   
3. 3 18 25 22 11
   
4. 4 19 20 21 10
   
5. 5  6  7  8  9

复制代码

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

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

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

复制代码

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

1. int fourmin(int a, int b, int c, int d){
   
2.         int abmin = min(a,b);
   
3.         int cdmin = min(c,d);
   
4.         return min(abmin,cdmin);
   
5. }

复制代码

接下来有了层数之后，我们就要统计这层以前所有层数的数量，并设置为初始值
那么一层一层来，我们知道一层的数量=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)层，所以说就可以设初始值了，写出代码（为了方便，直接--）

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

复制代码

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

1. if (d == x){
   
2. } else if (d == n-y+1){
   
3. } else if (d == n-x+1){
   
4. } else if (d == y){
   
5. }

复制代码

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

1. if (d == x){
   
2.         a += y-d;
   
3. } else if (d == n-y+1){
   
4.         a += (n-2*(d-1)-1)+(x-d);
   
5. } else if (d == n-x+1){
   
6.         a += 2*(n-2*(d-1)-1)+(n-d+1-y);
   
7. } else if (d == y){
   
8.         a += 3*(n-2*(d-1)-1)+(n-d+1-x);
   
9. }

复制代码

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

1. #include <iostream>
   
2. using namespace std;
   
3. int fourmin(int a, int b, int c, int d){
   
4.         int abmin = min(a,b);
   
5.         int cdmin = min(c,d);
   
6.         return min(abmin,cdmin);
   
7. }
   
8. int main(){
   
9.         int x, y, n;
   
10.         cin >> x >> y >> n;
    
11.         int d = fourmin(x, y, n-x+1, n-y+1);
    
12.         d--;
    
13.         int a = 4*(n*d-d-d*(d-1))+1;
    
14.         d++;
    
15.         if (d == x){
    
16.                 a += y-d;
    
17.         } else if (d == n-y+1){
    
18.                 a += (n-2*(d-1)-1)+(x-d);
    
19.         } else if (d == n-x+1){
    
20.                 a += 2*(n-2*(d-1)-1)+(n-d+1-y);
    
21.         } else if (d == y){
    
22.                 a += 3*(n-2*(d-1)-1)+(n-d+1-x);
    
23.         }
    
24.         cout << a;
    
25.         return 0;
    
26. }

复制代码

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

FishC

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

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

1. int fourmin(int a, int b, int c, int d){
   
2.         int abmin = min(a,b);
   
3.         int cdmin = min(c,d);
   
4.         return min(abmin,cdmin);
   
5. }

复制代码

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

1. if (d == x){
   
2.         a += y-d;
   
3. } else if (d == n-y+1){
   
4.         a += (n-2*(d-1)-1)+(x-d);
   
5. } else if (d == n-x+1){
   
6.         a += 2*(n-2*(d-1)-1)+(n-d+1-y);
   
7. } else if (d == y){
   
8.         a += 3*(n-2*(d-1)-1)+(n-d+1-x);
   
9. }

复制代码

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

1. cout << a;

复制代码

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

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int fourmin(int a, int b, int c, int d){
   
5.         int abmin = min(a,b);
   
6.         int cdmin = min(c,d);
   
7.         return min(abmin,cdmin);
   
8. }
   
9. 
   
10. int main(){
    
11.         int x, y, n;
    
12.         cin >> x >> y >> n;
    
13.        
    
14.         int d = fourmin(x, y, n-x+1, n-y+1);
    
15.         d--;
    
16.         int a = 4*(n*d-d-d*(d-1))+1;
    
17.         d++;
    
18.        
    
19.         if (d == x){
    
20.                 a += y-d;
    
21.         } else if (d == n-y+1){
    
22.                 a += (n-2*(d-1)-1)+(x-d);
    
23.         } else if (d == n-x+1){
    
24.                 a += 2*(n-2*(d-1)-1)+(n-d+1-y);
    
25.         } else if (d == y){
    
26.                 a += 3*(n-2*(d-1)-1)+(n-d+1-x);
    
27.         }
    
28.        
    
29.         cout << a;
    
30.        
    
31.         return 0;
    
32. }

复制代码

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

以上回复来自 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

尹玄睿

只是来回帖的

三体人的智子

好

一箭琼华陨

啊？