将矩阵元素映射到其螺旋阶遍历中的位置 [英] Mapping elements of a matrix to its position in its spiral order traversal

问题描述

我试图找到一个函数，该函数在矩阵(MXN)中采用一个单元格(x，y)的位置，并在该函数的螺旋阶遍历中给出其位置(1 <= p <= M * N)矩阵 .例如 : 对于M = 3，N = 3和矩阵:

[1,2,3]

[4,5,6]

[7,8,9]

螺旋阶遍历产生:{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)，得出该单元格在位置上的位置螺旋顺序遍历.

解决方案

让我们从查找单元格在哪个回合"开始.也就是说，螺旋在撞到该单元之前多久绕一次:

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

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.

解决方案

Let's start with finding in which "round" the cell is. That is, how often did the spiral go fully around before hitting this cell:

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

The first full round consists of 2*M + N) - 4 cells, the next one of 2*(M + N) - 12 cells, and so on (I hope you believe me in this). More general, round i consists of 2*(M + N - 2) - 8*i cells.

So how many cells are in the first n rounds? Just sum the value just found:

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)

We can already add this value to the index:

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

Now we just need to check where in the current round the cell is:

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

I called the method spiral(M, N, x, y) and ran it as follows:

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

Which results in

0
1
2
3
4
5
6
7
8

这篇关于将矩阵元素映射到其螺旋阶遍历中的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！