螺旋队列

 

    看清以上数字排列的规律,设1点的坐标是(0,0),x方向向右为正,y方向向下为正.例如:7的坐标为(-1,-1) ,2的坐标为(0,1),3的坐标为(1,1).编程实现输入任意一点坐标(x,y),输出所对应的数字。

    解析：规律能看出来，问题就在于如何利用它。很明显这个队列是顺时针螺旋向外扩展的，我们可以把它看成一层一层往外延伸：第 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)，如何知道该点处于第几层？层数 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

　　其实还有一点很重要，不然会有问题。其它三条边都还好，但是在东边（右边）那条线上，队列增加不完全符合公式！注意 到东北角（右上角）是本层的最后一个数，再往下却是本层的第一个数，那当然不满足东线公式啊。所以我们把东线的判断放在最后（其实只需要放在北线之后就可 以），这样一来，东北角那点始终会被认为是北线上的点。

答案：代码如下：

#include <stdio.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))

//x,y为横纵坐标，返回(x,y)点处的值
int foo(int x, int y)
{
    int t = max(abs(x), abs(y));//层数t = max(|x|,|y|)

    int u = t + t;//u为临时变量=2t
    int v = u - 1;//2t-1
    v = v * v + u;//(2t-1)^2+2t

    //v表示数值
    if (x == - t)//西|左：x == -t，队列增长方向和 y 轴相反，正西方向(y ＝ 0)
        v += u + t - y;//数值为(2t-1)^2+2t+2t+t-y = (2t-1)^2+5t
    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 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;
}

 

原文网站：http://blog.csdn.net/songxinkun/archive/2009/07/26/4381575.aspx