Определить значение элемента «спиральной матрицы» по его координатам

#java #алгоритм

                    
Недавно был вопрос об инициализации массива спиральной матрицей. Хотя предложенные
решения его решают, интересно решить эту задачу без использования памяти под массив,
а именно:


  Написать метод getNum(int s, int x, int y), который принимает три целых параметра
— размер квадратной матрицы (s) и координаты позиции в этой матрице (x, y от 0 до s-1)
и возвращает число от 1 до s*s, которое должно стоять в соответствующей ячейке «спиральной
матрицы» (сматывающейся от левого-верхнего угла к центру по часовой стрелке).


Тогда задача вывода данной матрицы на экран должна свестись к такому коду (никакой
массив не нужен):

for (int y = 0; y < s; y++) {
    for (int x = 0; x < s; x++) {
        System.out.printf("%4d", getNum(s, x, y));
    }
    System.out.println();
}


Кроме того можно вообще выводить огромные матрицы, в UI-окошке и скроллить мышкой,
быстро отрисовывая только видимую часть.

Как же реализовать такой метод?

Решения на других языках тоже принимаются.
    

Ответы

Ответ 1

Для начала переведём входные координаты x и y в систему координат относительно центра
матрицы. Так как размер может быть чётным или нечётным, удвоим координаты, чтобы не
возиться с половинками:

x = 2 * x - s + 1;
y = 2 * y - s + 1;


Скажем, для матрицы 5×5 возможные значения x и y будут -4, -2, 0, 2, 4. А для матрицы
6×6 — -5, -3, -1, 1, 3, 5.

Дальше определим, на каком квадрате от центра лежит текущая точка. Это просто максимум
модуля обеих координат:

int n = Math.max(Math.abs(x), Math.abs(y));


Скажем, для квадрата 5×5 значения будут такие:

4  4  4  4 *4
4  2  2 *2  4
4  2 *0  2  4
4  2  2  2  4
4  4  4  4  4


Заметим, что внутри текущего квадрата (n-1)*(n-1) записей. Попробуем определить,
какое число должно быть на правой-верхней диагонали. Надо из квадрата s*s вычесть квадрат
n*n и посмотреть, что получается. Оказывается, надо ещё n вычесть. Вот значения s*s-n*n-n
для квадрата 5×5:

5   5   5   5  *5
5  19  19 *19   5
5  19 *25  19   5
5  19  19  19   5
5   5   5   5   5


Ура, диагональ получили. С чётной стороной это тоже верно. Теперь посчитаем расстояние
от этой диагонали с учётом знака:

int p = (y + x) / 2;


Прибавим это расстояние к нашему s*s - n*n - n, получим:

1   2   3   4   5
2  17  18  19   6
3  18  25  20   7
4  19  20  21   8
5   6   7   8   9


Отлично, теперь весь правый-верхний треугольник мы правильно выдаём. Чтобы починить
левый-нижний, надо для него заменить p на 2*n-p. Точка лежит в левом-нижнем треугольнике,
если x < y:

if (x < y)
    p = 2 * n - p;


Вот полный код:

public static int getNum(int s, int x, int y) {
    x = 2 * x - s + 1;
    y = 2 * y - s + 1;
    int n = Math.max(Math.abs(x), Math.abs(y));
    int p = (x + y) / 2;
    if (x < y)
        p = 2 * n - p;
    return s * s - n * n - n + p;
}


Ответ 2

Вот чистое C без рекурсии, массивов и с двумя параметрами.
Самое элегантное решение, что мне удалось получить.
Левый верхний угол, индексация с нуля.

Вход:

0 1 2 
3 4 5
6 7 8


Выход:

0 1 2
7 8 3
6 5 4


Правда я его так и не проверил, могут быть ошибки, но идея состоит в том, чтобы просто
использовать явную формулу:

uint32_t spiral(uint32_t size, uint32_t index)
{   
    int x = 2 * (index % size) - size;
    int y = 2 * (index / size) - size;

    return (abs(x)>abs(y)) ? ((x>0) ? (4*x*x-3*x+y) : (4*x*x-x-y)) : ((y>0) ? (4*y*y-y-x)
: (4*y*y-3*y+x)); 
}