时间戳

首页 > 解决方案 > 查找在螺旋矩阵中行进的 N 个正方形的坐标

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

问题描述

我解决了一个在线判断问题（输入正确），但是我的算法太慢了。

我有一个可变大小的矩阵，并想找到行进n的正方形数量的坐标。在这个例子中，矩阵的大小是：。表示行数和列数。8

在此处输入图像描述

从点开始x, y： (1, 1) 和；

鉴于i = 53

通过到达计算坐标，从每个经过的方格开始n = 0并累加。1nn == i

我试过的：

（免责声明：我只是发布这个，所以你可以看到我是多么天真）

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

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到达的正方形数量。i53

这当然是非常幼稚的，因为在某些情况下，矩阵可能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;
}

标签： c++matrix

解决方案

是的，有一个模式。您可以从这个开始（您可能会遇到较大值的堆栈溢出问题，但如果您愿意，很容易替换递归） 

void GetSpiralFinalCoordinates(
    const unsigned long long s,
    const unsigned long long n,
    unsigned long long& x,
    unsigned long long& y) {

    // calculate max n for external ring 
    const unsigned long long maxN = s * 4 - 4;

    // if not in the external ring we will use recursion
    if (n > maxN) {
        unsigned long long subX;
        unsigned long long subY;
        GetSpiralFinalCoordinates(s - 2, n - maxN, subX, subY);
        x = subX + 1; 
        y = subY + 1;
        return;
    }
    if (n <= s) {
        x = n; 
        y = 1; 
        return;
    }
    if (n <= 2 * s - 1) {
        x = s; 
        y = n - s + 1;
        return;
    }
    if (n <= 3 * s - 2) {
        x = s - n + (2 * s - 1);
        y = s;
        return;
    }
    x = 1;
    y = 4 * s - n - 2; 
}

推荐阅读