螺旋排列
本帖最后由 lw2001 于 2020-2-15 21:40 编辑有一张地图，上面有编号1，2，...，n^2是从外层至中心按顺时针方向螺旋排列的点，相邻的点对距离都是1，现在给出两个编号a、b，问两个编号所对应的点之间的最短距离是多少？
举例：
n=3
http://acm.ticknet.hnust.cn/JudgeOnline/upload/201512/%E9%A2%98%E7%9B%AE%E5%9B%BE%E7%89%871.png
此图中，编号2和编号5的最短距离就是sqrt（1＋4)= 2.236。
如n = 5的时候，地图上点位置如下：
http://acm.ticknet.hnust.cn/JudgeOnline/upload/201512/%E9%A2%98%E7%9B%AE%E5%9B%BE%E7%89%872.png
如图中，编号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;
}
```
想请教一下程序有什么好的优化方向吗？
我想想看，稍后回复 没看明白代码，首先是定义一个数组M*N，然后赋值，可以迭代，首先是一圈的数字，然后下一个内圈，一直到1个为止
即先5*5的边4+4+4+4个数，然后是3*3的内圈，2+2+2+2个，然后是1*1的内圈
赋值完成后，给数即找出在数组中的坐标，长度即两点间距离， ymhld 发表于 2020-2-8 15:18
没看明白代码，首先是定义一个数组M*N，然后赋值，可以迭代，首先是一圈的数字，然后下一个内圈，一直到1个 ...
这样慢了，我就把数组去掉了，其实我想知道有没有直接有给定的值求螺旋矩阵中的该值的坐标的方法？如果可以有值找坐标的话应该可以快很多 没想出什么好办法，第一个是求在哪个层（圈）内，然后找出在哪条边，在四个边上的XY坐标计算方法不一样
#螺旋数组
#成功组成
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=num
print(a)
#pdb.set_trace() #断点测试
[[ 1.2.3.4.5.6.7.]
]
页:
[1]