给定其在螺旋上的位置，以二维数组查找元素 [英] Finding an element in a 2d array given its position on a spiral

问题描述

我正在尝试解决一个问题，该问题涉及矩阵元素的螺旋排序以及如何计算相应的行和列.

I am trying to solve a problem which involves a spiral ordering of the elements of a matrix and how to calculate the corresponding row and column.

所有查询的格式为SZ P，其中SZ是矩阵的大小，P是从中心开始到右上角的螺旋位置.
输出必须是螺旋中P点的笛卡尔坐标(行和列)(从底部的第1行开始，左侧为第1列开始).

All the queries are in the form SZ P, where SZ is the size of the matrix and P the position in spiral starting from the center and ending in the top right corner.
The output has to be the cartesian coordinates (row and column) of the P point in the spiral (starting with line 1 at the bottom and column 1 at the left).

我为解决该问题所做的事情是从右上角开始一直到中心为止，以相反的方式进行:

What I did to solve it, is doing it in reverse way, starting from the right corner and going on until the center):

while(k <= SZ && l <= SZ && m > 0 && n > 0)
{
right:
    for(int i = k; i <= m; ++i) /// right
    {
        a[i][m] = no;
        --no;
    }
    --m;
down:
    for(int i = m; i >= k; --i) /// down
    {
        a[n][i] = no;
        --no;
    }
    --n;
left:
    for(int i = n; i >= k; --i) /// left
    {
        a[i][k] = no;
        --no;
    }
    ++k;
up:
    for(int i = k; i <= m; ++i) /// up
    {
        a[l][i] = no;
        no--;
    }
    ++l;
    ///where l,k,n,m are:
    /// k start row index
    /// n end row index
    /// l start column index
    /// m end column index
}

代码在3x3矩阵上工作良好，它输出以下矩阵:

The code works well on a 3x3 matrix, it outputs this matrix:

3 2 9
4 1 8
5 6 7

因此，我现在要查找的是如何在矩阵中找到点P的笛卡尔坐标而不将矩阵存储在内存中，因为大小限制为100000.

So, what I'm trying to find out now is how to find the cartesian coordinates of the point P in matrix without storing the matrix in memory, because the size limit is 100000.

示例输入:

3 1
3 3
3 9
5 9
5 10

示例输出:

Line = 2, column = 2.
Line = 3, column = 1.
Line = 3, column = 3.
Line = 4, column = 4.
Line = 5, column = 4.

推荐答案

稍微扩大螺旋线，就会出现一种模式...

Augmenting the spiral slightly, a pattern emerges...

 31  30  29  28  27  26
 32  13  12  11  10 (25)
 33  14  03  02 (09) 24
 34  15 (04)[01] 08  23
 35 (16) 05  06  07  22
(36) 17  18  19  20  21

在东北向对角线上，奇数为1 ^ 2、3 ^ 2、5 ^ 2的平方，在西南向对角线上为偶数的平方.

Squares of odd numbers 1^2, 3^2, 5^2 are located on the NorthEast facing diagonal, and squares of even numbers on SouthWest facing diagonal.

在任何N ^ 2，(N + 1)^ 2之间，还有2N(+1)个元素；前N个位于水平线上，其余N个位于垂直线上.

Also between any N^2, (N+1)^2 there are 2N(+1) elements; the first N are located on horizontal line and the rest on vertical line.

将第一个项目(N = 1)放在x=0, y=0，第n个项目的坐标为:

Placing the first item (N=1) at x=0, y=0, the coordinate for nth item is:

void spiral_to_cartesian(int &x, int &y, int n)
{
    x = 0; y=0;
    if (n <= 1)  return;
    int a = sqrt((double)n);
    int remainder = n - a*a;
    if (a & 1)
    {
       x+=(a/2); y-=(a/2);
       if (remainder > 0 && remainder <= n)
       {
          --y; x-=remainder-1;
       }
       else if (remainder > n)
       {
          x-=n; y+=remainder - n - 1;
       }
    }
    else
    {
       x-=(a/2); y+=(a/2)-1;
       if (remainder > 0 && remainder <= n)
       {
          ++y; x+=remainder-1;
       }
       else if (remainder > n)
       {
          x+=n; y-=remainder - n - 1;
       }
    }
}

这篇关于给定其在螺旋上的位置，以二维数组查找元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！