Вращение двумерного массива на 90 градусов

Question

Частый вопрос, который возникает во время упражнений на манипуляции с массивами, - это поворот двумерного массива на 90 градусов. Есть несколько SO сообщений, которые отвечают, как это сделать на разных языках программирования. Мой вопрос состоит в том, чтобы уточнить один из ответов, которые там есть, и выяснить, какой тип мыслительного процесса необходим для того, чтобы получить ответ органичным образом.

Решение этой проблемы, которое я нашел, заключается в следующем:

public static void rotate(int[][] matrix,int n)
{
  for( layer = 0;layer < n/2;++layer){
      int first = layer;
      int last = n -1 - layer;
      for(int i = first;i<last;++i){
        int offset = i - first;
        int top = matrix[first][i];
        matrix[first][i] = matrix[last-offset][first];
        matrix[last-offset][first] = matrix[last][last-offset];
        matrix[last][last-offset] = matrix[i][last];
        matrix[i][last] = top;
       }
    }
}

У меня есть некоторое представление о том, что пытается сделать приведенный выше код: он меняет конечности / углы, выполняя четырехсторонний обмен и делая то же самое для других ячеек, разделенных некоторым смещением.

Проходя через этот код, я знаю, что он работает, но я не получаю математическую основу для приведенного выше алгоритма. Каково обоснование «слоя», «первого», «последнего» и смещения?

Каким образом «последний» оказался n-1-layer? Почему смещение i-first? Какое смещение в первую очередь?

Если бы кто-нибудь мог объяснить происхождение этого алгоритма и провести меня через мыслительный процесс, чтобы найти решение, это было бы здорово.

Спасибо

Answer 1

Идея состоит в том, чтобы разбить большую задачу (вращение квадратной матрицы) на более мелкие задачи.

Во-первых, квадратную матрицу можно разбить на концентрические квадратные кольца. Вращение кольца не зависит от вращения других колец, поэтому для вращения матрицы просто вращайте каждое из колец, одно за другим. В этом случае мы начинаем с самого дальнего кольца и работаем внутрь. Мы считаем кольца, используя layer (или first, то же самое), и останавливаемся, когда добираемся до середины, поэтому оно увеличивается до n/2. (Стоит проверить, чтобы убедиться, что это будет работать для нечетных и четных n.) Полезно отслеживать «дальний край» кольца, используя last = n - 1 - layer. Например, в матрице 5x5 первое кольцо начинается с first=0 и заканчивается на last=4, второе кольцо начинается с first=1 и заканчивается на last=3 и т. Д.

Как вращать кольцо? Идите прямо по верхнему краю, вверх по левому краю, налево вдоль нижнего края и вниз вдоль правого края, все одновременно. На каждом шаге меняйте местами четыре значения. Координата, которая изменяется, равна i, а число шагов - offset. Например, при обходе второго кольца i идет {1,2,3}, а offset идет {0,1,2}.