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;
}