螺旋排列

lw2001

有一张地图，上面有编号1，2，...，n^2是从外层至中心按顺时针方向螺旋排列的点，相邻的点对距离都是1，现在给出两个编号a、b，问两个编号所对应的点之间的最短距离是多少？
举例：
n=3

此图中，编号2和编号5的最短距离就是sqrt（1＋4)= 2.236。
如n = 5的时候，地图上点位置如下：

如图中，编号5和 编号13的最短距离就是sqrt（16＋16）= 5.657。


输入：
先输入一个T（T≤1000），表示数据组数。
接下来T行，每行包括3个正整数n，a，b(1≤n≤4500，1≤a，b≤n2)。
```
#include <stdio.h>
#include <math.h>

int main() {
    int t;
    int n;
    scanf("%d",&t);
    int a,b,c,d;
    int n1,n2;
    while (t--){
        scanf("%d%d%d",&n,&n1,&n2);
        int k=1;
        for (int i = 0; i < n / 2 + 1; ++i) {
            for (int j = i; j < n-i; ++j) {
                if(k==n1){
                    a=i;
                    b=j;
                } else if (k==n2){
                    c=i;
                    d=j;
                    goto ed;
                }
                k++;
            }
            for (int j = i+1; j < n-i; ++j) {
                if(k==n1){
                    a=j;
                    b=n-i-1;
                } else if (k==n2){
                    c=j;
                    d=n-i-1;
                    goto ed;
                }
                k++;
            }
            for (int j = n-i-1; j >i; --j) {
                if(k==n1){
                    a=n-i-1;
                    b=j-1;
                } else if (k==n2){
                    c=n-i-1;
                    d=j-1;
                    goto ed;
                }
                k++;
            }
            for (int j = n-i-1; j > i+1; --j) {
                if(k==n1){
                    a=j-1;
                    b=i;

                } else if (k==n2){
                    c=j-1;
                    d=i;
                    goto ed;
                }
                k++;
            }
        }
        ed:
        a-=c;
        b-=d;
        printf("%.3f\n",sqrt(a*a+b*b));
    }
    return 0;
}
```
想请教一下程序有什么好的优化方向吗？

badyun

我想想看，稍后回复

ymhld

没看明白代码，首先是定义一个数组M*N，然后赋值，可以迭代，首先是一圈的数字，然后下一个内圈，一直到1个为止
即先5*5的边4+4+4+4个数，然后是3*3的内圈，2+2+2+2个，然后是1*1的内圈
赋值完成后，给数即找出在数组中的坐标，长度即两点间距离，

lw2001

ymhld 发表于 2020-2-8 15:18
没看明白代码，首先是定义一个数组M*N，然后赋值，可以迭代，首先是一圈的数字，然后下一个内圈，一直到1个 ...

这样慢了，我就把数组去掉了，其实我想知道有没有直接有给定的值求螺旋矩阵中的该值的坐标的方法？如果可以有值找坐标的话应该可以快很多

ymhld

没想出什么好办法，第一个是求在哪个层（圈）内，然后找出在哪条边，在四个边上的XY坐标计算方法不一样

[Python] 纯文本查看 复制代码

#螺旋数组
#成功组成
import numpy as np
import pdb 


n=7
a=np.zeros((n,n))

for num in range(1,n**2+1):
	number=num
	flags=True
	cirx=0
	ciry=0
	cir=1			#求数字在几层内
	x=0
	y=0
	while flags:
		if cir==(int(n)+1)/2:
			flags=False
			cirx=1
			ciry=1
			x=cir
			y=cir
			break
		if number>4*(n+1-2*cir):	#每层的数字个数为4*n-1)
			number=number-4*(int(n)+1-2*cir)
			cir+=1
		else:
			#print(number,cirx,ciry)
			cirx=int(number/(n+1-2*cir))+1
			ciry=number%((n+1-2*cir))
			if ciry==0:
				cirx-=1
				ciry=(n+1-2*cir)
			if cirx==1:
				x=cir
				y=cir+ciry-1
			if cirx==2:
				y=n-cir+1
				x=cir+ciry-1
			if cirx==3:
				x=n-cir+1
				y=n-cir-ciry+2
			if cirx==4:
				y=cir
				x=n-cir-ciry+2
			break
	a[x-1,y-1]=num
print(a)
	#pdb.set_trace() #断点测试

[[ 1.  2.  3.  4.  5.  6.  7.]
[24. 25. 26. 27. 28. 29.  8.]
[23. 40. 41. 42. 43. 30.  9.]
[22. 39. 48. 49. 44. 31. 10.]
[21. 38. 47. 46. 45. 32. 11.]
[20. 37. 36. 35. 34. 33. 12.]
[19. 18. 17. 16. 15. 14. 13.]]