Как вы поворачиваете двумерный массив?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Вдохновленный Сообщение Рэймонда Чена, допустим, у вас есть двумерный массив размером 4x4, напишите функцию, которая поворачивает его на 90 градусов.Рэймонд ссылается на решение в псевдокоде, но я бы хотел увидеть кое-что из реального мира.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
Становится:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
Обновить:Ответ Ника самый простой, но есть ли способ сделать это лучше, чем n ^ 2?Что, если бы матрица была размером 10000x10000?
Решение
Вот это в C#
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
Другие советы
Алгоритм O (n^ 2) времени и O (1) пространства (без всяких обходных путей и всяких глупостей!)
Поворот на +90:
- Транспонировать
- Переверните каждый ряд
Повернуть на -90:
Способ 1 :
- Транспонировать
- Переверните каждый столбец
Способ 2 :
- Переверните каждый ряд
- Транспонировать
Поворот на +180:
Способ 1:Дважды поверните на +90
Способ 2:Переверните каждую строку, а затем переверните каждый столбец (транспонируйте)
Повернуть на -180:
Способ 1:Дважды поверните на -90
Способ 2:Переверните каждый столбец, а затем каждую строку
Способ 3:Поверните на + 180, так как они одинаковые
Я хотел бы добавить еще немного деталей.В этом ответе повторяются ключевые понятия, темп медленный и намеренно повторяющийся.Представленное здесь решение не является самым синтаксически компактным, однако оно предназначено для тех, кто хочет узнать, что такое вращение матрицы и результирующая реализация.
Во-первых, что такое матрица?Для целей этого ответа матрица - это просто сетка, ширина и высота которой одинаковы.Обратите внимание, что ширина и высота матрицы могут быть разными, но для простоты в этом руководстве рассматриваются только матрицы одинаковой ширины и высоты (квадратные матрицы).И да, матрицы является множественным числом от matrix.
Примерами матриц являются:2×2, 3×3 или 5×5.Или, в более общем смысле, N×N.Матрица 2 × 2 будет содержать 4 квадрата, потому что 2 × 2 = 4.Матрица 5 × 5 будет содержать 25 квадратов, потому что 5 × 5 = 25.Каждый квадрат называется элементом или записью.Мы будем обозначать каждый элемент точкой (.) на приведенных ниже диаграммах:
матрица 2 × 2
. .
. .
матрица 3 × 3
. . .
. . .
. . .
матрица 4 × 4
. . . .
. . . .
. . . .
. . . .
Итак, что значит вращать матрицу?Давайте возьмем матрицу 2 × 2 и поместим несколько чисел в каждый элемент, чтобы можно было наблюдать вращение:
0 1
2 3
Поворот этого элемента на 90 градусов дает нам:
2 0
3 1
Мы буквально один раз повернули всю матрицу вправо, точно так же, как поворачивают руль автомобиля.Это может помочь подумать о том, чтобы “перевернуть” матрицу на правую сторону.Мы хотим написать функцию на Python, которая принимает матрицу и поворачивает ее один раз вправо.Сигнатура функции будет выглядеть следующим образом:
def rotate(matrix):
# Algorithm goes here.
Матрица будет определена с помощью двумерного массива:
matrix = [
[0,1],
[2,3]
]
Следовательно, доступ к строке осуществляется из первой позиции индекса.Вторая позиция индекса позволяет получить доступ к столбцу:
matrix[row][column]
Мы определим служебную функцию для печати матрицы.
def print_matrix(matrix):
for row in matrix:
print row
Один из методов поворота матрицы заключается в том, чтобы делать это слой за слоем.Но что такое слой?Подумайте о луковице.Точно так же, как со слоями лука, по мере удаления каждого слоя мы продвигаемся к центру.Другие аналогии - это Матрешка или игра в "передай посылку".
Ширина и высота матрицы определяют количество слоев в этой матрице.Давайте будем использовать разные символы для каждого слоя:
Матрица 2 × 2 имеет 1 слой
. .
. .
Матрица размером 3 × 3 состоит из 2 слоев
. . .
. x .
. . .
Матрица 4 × 4 состоит из 2 слоев
. . . .
. x x .
. x x .
. . . .
Матрица размером 5 × 5 состоит из 3 слоев
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Матрица размером 6 × 6 состоит из 3 слоев
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
Матрица 7 × 7 состоит из 4 слоев
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
Вы можете заметить, что увеличение ширины и высоты матрицы на единицу не всегда увеличивает количество слоев.Взяв приведенные выше матрицы и сведя в таблицу слои и размеры, мы видим, что количество слоев увеличивается один раз на каждые два приращения ширины и высоты:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
Однако не все слои нуждаются во вращении.Матрица 1 × 1 одинакова до и после вращения.Центральный слой размером 1 × 1 всегда остается одним и тем же до и после поворота, независимо от размера общей матрицы:
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
Учитывая матрицу N × N, как мы можем программно определить количество слоев, которые нам нужно повернуть?Если мы разделим ширину или высоту на два и проигнорируем остаток, то получим следующие результаты.
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
Обратите внимание , как N/2 соответствует количеству слоев, которые нужно повернуть?Иногда количество вращаемых слоев на единицу меньше общего количества слоев в матрице.Это происходит, когда самый внутренний слой сформирован только из одного элемента (т. е.матрица 1 × 1) и, следовательно, ее не нужно поворачивать.Это просто игнорируется.
Несомненно, нам понадобится эта информация в нашей функции для поворота матрицы, поэтому давайте добавим ее сейчас:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Теперь мы знаем, что такое слои и как определить количество слоев, которые на самом деле нуждаются в вращении, как нам изолировать один слой, чтобы мы могли его вращать?Во-первых, мы проверяем матрицу от самого внешнего слоя внутрь до самого внутреннего слоя.Матрица размером 5 × 5 состоит всего из трех слоев и двух слоев, которые необходимо вращать:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Давайте сначала посмотрим на столбцы.Положение столбцов, определяющих самый внешний слой, предполагая, что мы считаем от 0, равно 0 и 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 и 4 также являются позициями строк для самого внешнего слоя.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Так будет всегда, поскольку ширина и высота одинаковы.Следовательно, мы можем определить позиции столбцов и строк слоя, используя всего два значения (а не четыре).
Двигаясь внутрь ко второму слою, позиции столбцов равны 1 и 3.И, да, вы уже догадались, то же самое касается строк.Важно понимать, что нам приходилось как увеличивать, так и уменьшать позиции строк и столбцов при переходе внутрь к следующему слою.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
Итак, для проверки каждого слоя нам нужен цикл с увеличивающимися и уменьшающимися счетчиками, которые представляют движение внутрь, начиная с самого внешнего слоя.Мы назовем это нашим ‘циклом слоев’.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
Приведенный выше код перебирает позиции (строк и столбцов) любых слоев, которые нуждаются в вращении.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Теперь у нас есть цикл, обеспечивающий расположение строк и столбцов каждого слоя.Переменные first и last определите положение индекса первой и последней строк и столбцов.Возвращаясь к нашим таблицам строк и столбцов:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Таким образом, мы можем перемещаться по слоям матрицы.Теперь нам нужен способ навигации внутри слоя, чтобы мы могли перемещать элементы по этому слою.Обратите внимание, элементы никогда не ‘перепрыгивают’ с одного слоя на другой, но они перемещаются внутри своих соответствующих слоев.
Вращение каждого элемента в слое приводит к вращению всего слоя.Поворот всех слоев в матрице приводит к вращению всей матрицы.Это предложение очень важно, поэтому, пожалуйста, приложите все усилия, чтобы понять его, прежде чем двигаться дальше.
Теперь нам нужен способ фактического перемещения элементов, т.е.поверните каждый элемент, а затем слой и, в конечном счете, матрицу.Для простоты мы вернемся к матрице 3x3, которая имеет один вращающийся слой.
0 1 2
3 4 5
6 7 8
Наш цикл слоев предоставляет индексы первого и последнего столбцов, а также первой и последней строк:
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
Поскольку наши матрицы всегда квадратные, нам нужны всего две переменные, first и last, поскольку позиции индекса одинаковы для строк и столбцов.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
Переменные first и last можно легко использовать для ссылки на четыре угла матрицы.Это связано с тем, что сами углы могут быть определены с использованием различных перестановок first и last (без вычитания, сложения или смещения этих переменных):
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
По этой причине мы начинаем наше вращение с четырех внешних углов — сначала мы повернем их.Давайте выделим их с помощью *.
* 1 *
3 4 5
* 7 *
Мы хотим поменять местами каждый * с помощью * справа от него.Итак, давайте продолжим распечатку наших углов, определенных с использованием только различных перестановок first и last:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
Результат должен быть:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Теперь мы могли бы довольно легко поменять местами каждый из углов внутри нашего цикла слоев:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
Матрица перед поворотом углов:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Матрица после поворота углов:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Отлично!Мы успешно повернули каждый угол матрицы.Но мы не поворачивали элементы в середине каждого слоя.Очевидно, что нам нужен способ итерации внутри слоя.
Проблема в том, что единственный цикл в нашей функции на данный момент (наш цикл слоя) переходит к следующему слою на каждой итерации.Поскольку наша матрица имеет только один поворотный слой, цикл слоев завершается после поворота только углов.Давайте посмотрим, что происходит с матрицей большего размера, 5 × 5 (где требуется вращение двух слоев).Код функции был опущен, но он остается тем же, что и выше:
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
Результатом является:
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
Неудивительно, что углы самого внешнего слоя были повернуты, но вы также можете заметить, что углы следующего слоя (внутрь) также были повернуты.В этом есть смысл.Мы написали код для навигации по слоям, а также для поворота углов каждого слоя.Это похоже на прогресс, но, к сожалению, мы должны сделать шаг назад.Просто нет смысла переходить к следующему слою, пока предыдущий (внешний) слой не будет полностью повернут.То есть до тех пор, пока каждый элемент в слое не будет повернут.Поворачивать только углы не годится!
Сделайте глубокий вдох.Нам нужен еще один цикл.Вложенный цикл, не меньше.Новый вложенный цикл будет использовать first и last переменные плюс смещение для навигации внутри слоя.Мы назовем этот новый цикл нашим ‘циклом элементов’.Цикл элементов будет проходить по каждому элементу в верхнем ряду, по каждому элементу вниз с правой стороны, по каждому элементу вдоль нижнего ряда и по каждому элементу вверх с левой стороны.
- Перемещение вперед по верхней строке требует увеличения индекса столбца .
- Перемещение вниз по правой стороне требует, чтобы индекс строки был увеличен.
- Для перемещения назад по нижней части требуется, чтобы индекс столбца уменьшался.
- Перемещение вверх по левой стороне требует, чтобы индекс строки был уменьшен.
Это звучит сложно, но это делается легко, потому что количество раз, которое мы увеличиваем и уменьшаем для достижения вышеуказанного, остается одинаковым по всем четырем сторонам матрицы.Например:
- Переместите 1 элемент через верхний ряд.
- Переместите 1 элемент вниз по правой стороне.
- Переместите 1 элемент назад по нижнему ряду.
- Переместите 1 элемент вверх по левой стороне.
Это означает, что мы можем использовать одну переменную в сочетании с first и last переменные для перемещения внутри слоя.Возможно, полезно отметить, что перемещение по верхнему ряду и вниз по правой стороне требует увеличения.При движении назад вдоль нижней и вверх по левой стороне требуется уменьшение как того, так и другого.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
Теперь нам просто нужно назначить верхнюю часть правой стороне, правую сторону нижней, нижнюю часть левой стороне и левую сторону верхней.Сложив все это вместе, мы получаем:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
Учитывая матрицу:
0, 1, 2
3, 4, 5
6, 7, 8
Наш rotate функция приводит к:
6, 3, 0
7, 4, 1
8, 5, 2
Питон:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
Дешево, я знаю.
И против часовой стрелки:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Как это работает: (Запрошено в комментариях)
zip(*original) поменяет местами оси 2d-массивов, сложив соответствующие элементы из списков в новые списки.(Тот самый * operator сообщает функции распределить содержащиеся списки по аргументам)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
Тот Самый [::-1] оператор переворачивает элементы массива (пожалуйста, смотрите Расширенные Срезы).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
Наконец, объединение этих двух факторов приведет к преобразованию вращения.
Изменение в размещении [::-1] поменяет местами списки на разных уровнях матрицы.
Вот один из них, который выполняет вращение на месте вместо использования совершенно нового массива для хранения результата.Я прекратил инициализацию массива и распечатку его.Это работает только для квадратных массивов, но они могут быть любого размера.Накладные расходы на память равны размеру одного элемента массива, поэтому вы можете выполнять вращение сколь угодно большого массива.
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
Здесь масса хорошего кода, но я просто хочу показать, что происходит геометрически, чтобы вы могли немного лучше понять логику кода.Вот как бы я подошел к этому.
прежде всего, не путайте это с транспозицией, которая очень проста..
основная идея состоит в том, чтобы обрабатывать его как слои, и мы поворачиваем по одному слою за раз..
допустим, у нас есть 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
после того как мы повернем его по часовой стрелке на 90, мы получим
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
итак, давайте разложим это по полочкам, сначала мы существенно повернем 4 угла
1 4
13 16
затем мы вращаем следующий ромб, который немного перекошен
2
8
9
15
а затем 2-й перекошенный ромб
3
5
12
14
таким образом, это заботится о внешнем крае, поэтому, по сути, мы делаем это по одной оболочке за раз, пока
наконец, средний квадрат (или, если это странно, просто последний элемент, который не перемещается)
6 7
10 11
итак, теперь давайте выясним индексы каждого слоя, предположим, что мы всегда работаем с самым внешним слоем, который мы делаем
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
так далее и так далее пока мы не окажемся на полпути к краю
итак, в целом картина такова
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
Как я уже говорил в своем предыдущем посте, вот некоторый код на C #, который реализует вращение матрицы O (1) для матрицы любого размера.Для краткости и удобочитаемости здесь нет проверки ошибок или диапазона.Код:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
Хорошо, я поднимаю руку, на самом деле это не вносит никаких изменений в исходный массив при вращении.Но в OO-системе это не имеет значения, пока объект выглядит так, как будто он был передан клиентам класса.На данный момент класс Matrix использует ссылки на исходные данные массива, поэтому изменение любого значения m1 также изменит m2 и m3.Небольшое изменение в конструкторе для создания нового массива и копирования в него значений позволит решить эту проблему.
Хотя может потребоваться вращение данных на месте (возможно, для обновления физически сохраненного представления), становится проще и, возможно, более производительным добавить уровень косвенности в доступ к массиву, возможно, интерфейс:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Если ваш Matrix уже реализует этот интерфейс, то его можно поворачивать с помощью декоратор класс, подобный этому:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
Поворот +90/-90/180 На градусы, переключение по горизонтали / вертикали и масштабирование также могут быть достигнуты этим способом.
Производительность должна быть измерена в вашем конкретном сценарии.Однако операция O (n ^ 2) теперь была заменена вызовом O (1).Это вызов виртуального метода, который является медленнее, чем прямой доступ к массиву, поэтому это зависит от того, как часто используется повернутый массив после поворота.Если его использовать один раз, то такой подход определенно выиграет.Если его вращать, а затем использовать в системе с длительной эксплуатацией в течение нескольких дней, то вращение на месте может работать лучше.Это также зависит от того, сможете ли вы принять первоначальную стоимость.
Как и во всех проблемах с производительностью, измеряйте, измеряйте, измеряйте!
Это лучшая его версия на Java:Я сделал это для матрицы с другой шириной и высотой
- h - здесь высота матрицы после поворота
- w - здесь ширина матрицы после поворота
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
Этот код основан на сообщении Ника Берарди.
Рубиновый путь: .transpose.map &:reverse
Уже есть много ответов, и я нашел два, требующие O (1) временной сложности.Тот Самый реальный O (1) алгоритм состоит в том, чтобы оставить хранилище массива нетронутым и изменить способ индексации его элементов.Цель здесь состоит в том, чтобы он не потреблял дополнительной памяти и не требовал дополнительного времени для перебора данных.
Повороты на 90, -90 и 180 градусов - это простые преобразования, которые можно выполнять, если вы знаете, сколько строк и столбцов в вашем 2D-массиве;Чтобы повернуть любой вектор на 90 градусов, поменяйте местами оси и сведите ось Y на нет.При -90 градусах поменяйте местами оси и сведите ось X к нулю.Поверните обе оси на 180 градусов, не меняя их местами.
Возможны дальнейшие преобразования, такие как зеркальное отображение по горизонтали и /или вертикали путем независимого отрицания осей.
Это может быть сделано, например, с помощьюметод доступа.Приведенные ниже примеры представляют собой функции JavaScript, но эти концепции в равной степени применимы ко всем языкам.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);Этот код предполагает наличие массива вложенных массивов, где каждый внутренний массив представляет собой строку.
Метод позволяет считывать (или записывать) элементы (даже в случайном порядке), как если бы массив был повернут или преобразован.Теперь просто выберите нужную функцию для вызова, возможно, по ссылке, и вперед!
Концепция может быть расширена для применения преобразований аддитивно (и неразрушающе) с помощью методов доступа.Включая произвольные повороты на угол и масштабирование.
Пара человек уже привели примеры, которые включают в себя создание нового массива.
Еще несколько вещей, которые следует учитывать:
(a) Вместо фактического перемещения данных, просто пройдите по "повернутому" массиву по-другому.
(б) Выполнение вращения на месте может быть немного сложнее.Вам понадобится немного свободного места (вероятно, размером примерно с одну строку или столбец).Есть древняя статья ACM о выполнении транспонирования на месте (http://doi.acm.org/10.1145/355719.355729), но их пример кода - это отвратительный FORTRAN, перегруженный goto.
Добавление:
http://doi.acm.org/10.1145/355611.355612 это еще один, предположительно превосходный, алгоритм транспонирования на месте.
У Ника ответ будет работать и для массива NxM, только с небольшой модификацией (в отличие от NxN).
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
Один из способов подумать об этом заключается в том, что вы переместили центр оси (0,0) из верхнего левого угла в верхний правый угол.Вы просто переходите от одного к другому.
Время - O (N), Пространство - O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
Вот моя версия Ruby (обратите внимание, что значения отображаются по-разному, но она по-прежнему вращается, как описано).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
Результат:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
вот метод поворота в пространстве, разработанный Java, только для square.для неквадратичного 2d-массива вам все равно придется создать новый массив.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
код для поворота 2d-массива любого размера путем создания нового массива:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
Реализация псевдокода dimple +90 (например,транспонировать, а затем перевернуть каждую строку) в JavaScript:
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
Вы можете сделать это в 3 простых шага:
1) Предположим, у нас есть матрица
1 2 3
4 5 6
7 8 9
2) Возьмем транспонирование матрицы
1 4 7
2 5 8
3 6 9
3) Поменяйте местами строки, чтобы получить повернутую матрицу
3 6 9
2 5 8
1 4 7
Java исходный код для этого:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
Выходной сигнал:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
Это моя реализация, в C, O (1) сложность памяти, при повороте на 90 градусов по часовой стрелке:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
Вот версия Java:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = 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] = temp;
}
}
}
этот метод заключается в том, что сначала поворачивают самый верхний слой, затем последовательно переходят к внутреннему слою.
С линейной точки зрения рассмотрим матрицы:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
Теперь сделайте транспонирование
1 4 7
A' = 2 5 8
3 6 9
И рассмотрим действие A' на B или B на A'.
Соответственно:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
Это можно расширить для любой матрицы n x n.И быстрое применение этой концепции в коде:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
Код на C # для поворота [n, m] 2D массивов на 90 градусов вправо
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
Результат:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X - это размер массива, в котором находится изображение.
#transpose - это стандартный метод класса Array в Ruby, таким образом:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
Реализация представляет собой функцию транспонирования n ^ 2, написанную на C.Вы можете увидеть это здесь:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose выбрав "нажать, чтобы переключить источник" рядом с "транспонировать".
Я помню решения лучше, чем O (n ^ 2), но только для специально сконструированных матриц (таких как разреженные матрицы)
Код C для поворота матрицы на 90 градусов по часовой стрелке на МЕСТЕ для любой матрицы M * N
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
вот моя реализация на Месте на C
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
Вот моя попытка повернуть матрицу на 90 градусов, которая является двухэтапным решением на C.Сначала переместите матрицу на место, а затем поменяйте местами столбцы.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@dagorym:О, чувак.Я цеплялся за это как за хорошую головоломку типа "Мне скучно, над чем я могу поразмыслить".Я придумал свой код транспозиции на месте, но, придя сюда, обнаружил, что ваш практически идентичен моему ... Ну что ж.Вот это в Ruby.
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
Простой метод C ++, хотя в большом массиве были бы большие затраты памяти.
