Задача: 59. Spiral Matrix II
Сложность: medium

Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.

Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

👨‍💻 Алгоритм:

1⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.

3⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎 Решение:

class Solution {
    // Helper function to handle negative indices in modulo operations
    private function floorMod($x, $y) {
        return (($x % $y) + $y) % $y;
    }

    // Function to generate an n x n matrix in spiral order
    public function generateMatrix($n) {
        $result = array_fill(0, $n, array_fill(0, $n, 0));
        $cnt = 1;
        $dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        $d = 0;
        $row = 0;
        $col = 0;

        while ($cnt <= $n * $n) {
            $result[$row][$col] = $cnt;
            $cnt++;
            $r = $this->floorMod($row + $dir[$d][0], $n);
            $c = $this->floorMod($col + $dir[$d][1], $n);

            if ($result[$r][$c] != 0) {
                $d = ($d + 1) % 4;
            }
            
            $row += $dir[$d][0];
            $col += $dir[$d][1];
        }

        return $result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний