arrays - 将矩阵的元素映射到它在螺旋顺序遍历中的位置

Question

我试图找到一个函数，它获取矩阵 (MXN) 中单元格 (x,y) 的位置，并在矩阵 。例如 : 对于 M = 3、N = 3 和矩阵:

[1,2,3]

[4,5,6]

[7,8,9]

Spiral Order Traversal yields : { 1,2,3,6,9,8,7,4,5 } ，所以如果函数用 F(x,y) 表示，那么:

F(1,1) = 1、F(1,2) = 2、F(1,3) = 3、F(2,3) = 6、.. 等等。

所以基本上我需要一个封闭式公式，它对于给定的 M、N 和位置 (x,y) 产生该单元格在螺旋顺序遍历。

Answer 1

让我们从找出单元格在哪个“圆”中开始。也就是说，螺旋在击中此单元格之前绕完一圈的频率:

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