1

I am trying to find a function which takes the position of a cell(x,y) in the matrix(MXN) and gives its position(1<=p<=M*N) in the spiral order traversal of the matrix . For example : for M = 3, N = 3 , and matrix :

[1,2,3]

[4,5,6]

[7,8,9]

Spiral Order Traversal yields : { 1,2,3,6,9,8,7,4,5 } , so if the function is denoted by F(x,y) , then :

F(1,1) = 1 , F(1,2) = 2, F(1,3) = 3, F(2,3) = 6 , .. , and so on.

So basically I need a closed form formula which for a given M,N, and a position (x,y) , yields the position of that cell in the spiral order traversal.

4

2 回答 2

3

让我们从找出细胞在哪个“圆”中开始。也就是说，螺旋在撞击这个单元之前多久完全旋转一次：

int n = min(x, y, M - x - 1, N - y - 1);

第一个完整的回合由2*M + N) - 4细胞组成，下一个由2*(M + N) - 12细胞组成，依此类推（我希望你相信我）。更一般地说，轮i由2*(M + N - 2) - 8*i单元组成。

n那么第一轮有多少个细胞呢？只需将刚刚找到的值相加即可：

sum(0 <= i < n : 2*(M + N - 2) - 8*i) = 2*n*(M + N - 2) - 8 * sum(0 <= i < n : i)
                                      = 2*n*(M + N - 2) - 8 * n * (n - 1) / 2
                                      = 2*n*(M + N - 2*n)

我们已经可以将此值添加到索引中：

int index  = 2 * n * (M + N - 2 * n);

现在我们只需要检查当前回合中单元格的位置：

if (n == y) {
    // top of this round
    index += x - n;
} else {
    // add full top of this round
    index += M - 2 * n;

    if (n == M - x - 1) {
        // right side of this round
        index += y - (n + 1);
    } else {
        // add full right side  of this round
        index += N - 2 * n - 1;

        if (n == N - y - 1) {
            // bottom of this round
            index += N - x - 1 - (n + 1);
        } else {
            // add full bottom of this round
            index += M - 2 * n - 1;

            // left side of this round
            index += M - y - 1 - (n+1);
        }
    }
}

我调用了该方法spiral(M, N, x, y)并按如下方式运行它：

System.out.println(spiral(3, 3, 0, 0));
System.out.println(spiral(3, 3, 1, 0));
System.out.println(spiral(3, 3, 2, 0));
System.out.println(spiral(3, 3, 2, 1));
System.out.println(spiral(3, 3, 2, 2));
System.out.println(spiral(3, 3, 1, 2));        
System.out.println(spiral(3, 3, 0, 2));
System.out.println(spiral(3, 3, 0, 1));
System.out.println(spiral(3, 3, 1, 1));

这导致

0
1
2
3
4
5
6
7
8
于 2013-09-13T12:40:10.377 回答
0

好的，我想到了一个解决方案。我还没有编写任何代码来测试它，但也许稍后如果我下班回家我可以测试它以 100% 确定。

在算法中你需要做的第一件事是弄清楚你的位置在哪个季度。例如，在您的矩阵中，矩阵的中心不在任何四分之一，但您始终可以知道该点在哪个轴上。一般的想法是弄清楚点离侧面有多远，那么需要多少个完整的电路才能到达我们正在寻找的点。

在我们计算出我们离边多远之后（应该很容易得到 x 和 y 以及我们所在的季度和矩阵的大小），我们可以使用这个公式来计算遍历中使用的位置数以创建这些电路。（n是从侧面的距离）

sum = 2n * (M - 2n + N)

如果我们有用于到达赛道的位置数量，这是我们现在正在寻找的点，唯一的事情就是弄清楚我们在赛道上离这一点有多远。我认为它应该很容易通过我们位于哪个季度的知识来计算。

于 2013-09-13T12:41:41.037 回答