c++ - 查找在螺旋矩阵中行进的 N 个正方形的坐标

Question

我解决了一个 online judge problem (输入正确)，但是我的算法太慢了。

我有一个大小可变的矩阵，想要找到 n 个正方形的坐标 traveled。在此示例中，矩阵的大小为:8。表示行数和列数。

从点 x, y 开始:(1, 1) and;

• 尽可能向右走
• 尽可能向下
• 尽可能向左走
• 尽可能向上

假设 i = 53

从 n = 0 开始，将 1 加到 n 上，到达 n == i 计算坐标。

我尝试过的:

(免责声明:我发布这个只是为了让你看到我是多么天真)

在我最初的编程问题中，我通过创建一个变量 m 来实现它，该变量具有矩阵的大小，所以在这种情况下 m = 8，并在每个之后推导它右和左移动。

y = 0 //y will move first, starts offboard at imaginary column `0`
x = 1 //start from row 1
m = 8
right: { y+= i; m -= 1;} //x = 1, y = 8 / m = 7
down: {  x+= m; }//x = 8, y = 8
left: { y-= m; m -= 1; } //x = 8, y = 1 / m = 6
up: { x-=m; } // x = 2, y = 1

然后迭代，直到另一个创建的变量 sumofsteps，总计 m 行进的方 block 数量达到 i，在这种情况下 53.''

这当然是非常幼稚的，因为在某些情况下，矩阵可能与 1073741824 和步数一样大 1152921504603393520，这在我的程序中也需要长期解决。

单个输入的程序运行时间限制为 1.0 秒。

有没有更快的方法找到坐标？

#include <iostream>
#include <sstream>

void GetSpiralFinalCoordinates(
const unsigned long long gridSize, 
const unsigned long long finalDestSteps, 
unsigned long long& x, unsigned long long& y)
{
    x = 1;
    y = 0;
    unsigned long long stepsWalked{0};
    unsigned long long currentStepsToWalk = gridSize;
    enum movedir {RIGHT = 0, DOWN, LEFT, UP};

    while(stepsWalked < finalDestSteps)
    {
        for(int i=0; i<4; i++)
        {
            if(stepsWalked + currentStepsToWalk < finalDestSteps)
            {
                stepsWalked += currentStepsToWalk;
                switch(i)
                {
                    case RIGHT: { y+= currentStepsToWalk; currentStepsToWalk -= 1;}break;
                    case DOWN: {  x+= currentStepsToWalk; }break;
                    case LEFT: { y-= currentStepsToWalk; currentStepsToWalk -= 1; }break;
                    case UP: { x-=currentStepsToWalk; }break;
                }
            } else {
                int lastAmountOfStepsToWalk = finalDestSteps - stepsWalked;
                switch(i)
                {
                    case RIGHT: { y+= lastAmountOfStepsToWalk; }break;
                    case DOWN: {  x+= lastAmountOfStepsToWalk; }break;
                    case LEFT: { y-= lastAmountOfStepsToWalk; }break;
                    case UP: { x-=lastAmountOfStepsToWalk; }break;
                }
                stepsWalked = finalDestSteps + 1;
                break;
            }
        }
    }
}

int main()
{
    unsigned long long x, y;
    unsigned long long a, b;
    std::string line;
    std::getline(std::cin, line);
    std::istringstream issline(line);
    issline >> a;
    issline >> b;
    GetSpiralFinalCoordinates(a,b, x, y);
    std::cout << x << " " << y << std::endl;
}

Answer 1

考虑矩阵的“周长”。我们可以计算外壳中的细胞数为

P0 = 2 * rows + 2 * cols - 4

如果我们考虑内部的正方形单元格，我们可以说

P1 = 2 * (rows - 2) + 2 * (cols - 2) - 4 = P0 - 8

所以，直到两边都大于 1，我们可以找到这些值的总和

sumi = (i + 1) * P0 - 4 * i * (i + 1)

您可以使用这些公式“剥离”矩阵的外部，也就是说，找到 i 的值

总和_i < n < 总和_i+1

然后您可以使用您已经拥有的代码来完成最后的步骤。