C語言寫螺旋隊列
21 22 ....
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
看清以上數字排列的規律，設 1 點的坐標是 (0,0)，x 方向向右為正，y 方向向下為正。例如，7 的坐標為 (-1,-1)，2 的坐標為 (0,1)，3 的坐標為 (1,1)。編程實現輸入任意一點坐標 (x,y)，輸出所對應的數字。［Finland 某著名通信設備公司 2005 年面試題］
規律是什麼？規律真的一看就能看出來，問題就在於如何利用它。很明顯這個隊列是順時針螺旋向外擴展的，我們可以把它看成一層一層往外延伸。第 0 層規定為中間的那個 1，第 1 層為 2 到 9，第 2 層為 10 到 25，……好像看出一點名堂來了？注意到 1、9、25、……不就是平方數嗎？而且是連續奇數（1、3、5、……）的平方數。這些數還跟層數相關，推算一下就可以知道第 t 層之內一共有 (2t-1)^2 個數，因而第 t 層會從 [(2t-1)^2] + 1 開始繼續往外螺旋。給定坐標 (x,y)，如何知道該點處於第幾層？so easy，層數 t = max(|x|,|y|)。
知道了層數，接下來就好辦多了，這時我們就知道所求的那點一定在第 t 層這個圈上，順著往下數就是了。要注意的就是螺旋隊列數值增長方向和坐標軸正方向並不一定相同。我們可以分成四種情況——上、下、左、右——或者——東、南、西、北，分別處於四條邊上來分析。
東|右：x == t，隊列增長方向和 y 軸一致，正東方向（y = 0）數值為 (2t-1)^2 + t，所以 v = (2t-1)^2 + t + y
南|下：y == t，隊列增長方向和 x 軸相反，正南方向（x ＝ 0）數值為 (2t-1)^2 + 3t，所以 v ＝ (2t-1)^2 + 3t - x
西|左：x == -t，隊列增長方向和 y 軸相反，正西方向（y ＝ 0）數值為 (2t-1)^2 + 5t，所以 v = (2t-1)^2 + 5t - y
北|上：y == -t，隊列增長方向和 x 軸一致，正北方向（x ＝ 0）數值為 (2t-1)^2 + 7t，所以 v ＝ (2t-1)^2 + 7t + x
其實還有一點很重要，不然會有大 bug。其它三條邊都還好，但是在東邊（右邊）那條線上，隊列增加不完全符合公式！注意到東北角（右上角）是本層的最後一個數，再往下卻是本層的第一個數，那當然不滿足東線公式啊。怎麼辦？好辦。反正其它三條都滿足不是嗎，我們把東線的判斷放在最後（其實只需要放在北線之後就可以），這樣一來，東北角那點始終會被認為是北線上的點啦～
#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
int foo(int x,int y){
int t=max(abs(x),abs(y));
int u=t+t;
int v=u-1;
v=v*v+u;
if(x==-t)
v+=u+t-y;
else if(y==-t)
v+=3*u+x-t;
else if(y==t)
v+=t-x;
else
v+=y-t;
return v;
}
int main (int argc,char *argv[])
{
int x,y;
for(y=-4;y<=4;y++){
for(x=-4;x<=4;x++)
printf("%5d",foo(x,y));
printf("\n");
}
while(scanf("%d%d",&x,&y)==2)
printf("%d\n",foo(x,y));
return 0;
}
