Найти координаты N квадратов, пройденных по спиральной матрице

Question

Я решил проблему онлайн-судьи (входные данные верны), однако мой алгоритм слишком медленный.

У меня есть матрица переменных размеров, и я хочу найти координатыn количество квадратов пройдено . В этом примере размер матрицы: 8. Значение количества строк и столбцов.

Начиная с точки x, y: (1, 1) и;

• Как можно дальше вправо насколько возможно
• Как далеко вниз насколько возможно
• Как далеко влево насколько это возможно
• Как можно дальше вверх насколько возможно

Учитывая, что i = 53

Начиная с n = 0 и добавляя 1 кn для каждого пройденного квадрата, достигнув n == i, вычислите координаты.

Что я пробовал:

(Отказ от ответственности: я только публикую это такВы можете видеть, насколько я наивен)

В моей первоначальной задаче программирования я достиг ее путем создания переменной m с размером матрицы, как в данном случае m = 8, и выведения ее после каждого right и left движений .

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 квадратов i, которыев этом case 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

Рассмотрим «периметр» матрицы. Мы можем вычислить количество ячеек во внешней оболочке как

P<sub>0</sub> = 2 * rows + 2 * cols - 4

Если мы рассмотрим квадрат ячеек непосредственно внутри, мы можем сказать

P<sub>1</sub> = 2 * (rows - 2) + 2 * (cols - 2) - 4 = P<sub>0</sub> - 8

Итак, пока обе стороны не станут большезатем 1, мы можем найти сумму этих значений как

sum<sub>i</sub> = (i + 1) * P<sub>0</sub> - 4 * i * (i + 1)

. Вы можете использовать эти формулы, чтобы «очистить» внешнюю часть матрицы, то есть найти значение i , такоечто

сумма _i i + 1

Тогда вы можете использовать код, который вам уже нужен, чтобы пройти последние шаги.

Answer 2

Да, есть шаблон. Вы можете начать с этого (у вас может быть проблема переполнения стека для большого значения, но при желании легко заменить рекурсию)

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