Raymond Chen의 게시물 에서 영감을 받아 4×4 2 차원 배열이 있다고 가정하고 90도 회전하는 함수를 작성하십시오. Raymond는 의사 코드의 솔루션에 연결하지만 실제 상황을보고 싶습니다.
[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]
업데이트 : Nick의 대답이 가장 간단하지만 n ^ 2보다 더 나은 방법이 있습니까? 행렬이 10000×10000이면 어떻게 되나요?
답변
여기 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만큼 회전
답변
좀 더 자세하게 설명하고 싶습니다. 이 답변에서 핵심 개념이 반복되고 속도가 느리고 의도적으로 반복됩니다. 여기에 제공된 솔루션은 구문 적으로 가장 컴팩트하지는 않지만 매트릭스 회전이 무엇인지, 구현 결과를 배우려는 사람들을위한 것입니다.
첫째, 행렬이란 무엇입니까? 이 답변의 목적을 위해, 행렬은 너비와 높이가 동일한 그리드 일뿐입니다. 행렬의 너비와 높이는 다를 수 있지만 간단하게하기 위해이 자습서에서는 너비와 높이가 동일한 행렬 ( 제곱 행렬 ) 만 고려합니다 . 그리고 그렇습니다, 행렬 은 복수의 행렬입니다.
매트릭스의 예는 2 × 2, 3 × 3 또는 5 × 5이다. 또는 더 일반적으로, NxN. 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
문자 그대로 자동차의 핸들을 돌리는 것처럼 전체 매트릭스를 오른쪽으로 한 번 돌 렸습니다. 매트릭스를 오른쪽에 “팁”하는 것이 도움이 될 수 있습니다. 파이썬에서 행렬을 가져 와서 오른쪽으로 한 번 회전하는 함수를 작성하려고합니다. 함수 서명은 다음과 같습니다.
def rotate(matrix):
# Algorithm goes here.
행렬은 2 차원 배열을 사용하여 정의됩니다.
matrix = [
[0,1],
[2,3]
]
따라서 첫 번째 인덱스 위치는 행에 액세스합니다. 두 번째 인덱스 위치는 열에 액세스합니다.
matrix[row][column]
행렬을 인쇄하는 유틸리티 함수를 정의하겠습니다.
def print_matrix(matrix):
for row in matrix:
print row
매트릭스를 회전시키는 한 가지 방법은 한 번에 레이어를 만드는 것입니다. 그러나 레이어는 무엇입니까? 양파를 생각하십시오. 양파의 레이어와 마찬가지로 각 레이어가 제거되면 중앙으로 이동합니다. 다른 유추는 Matryoshka 인형 또는 패스 소포 게임입니다.
행렬의 너비와 높이는 해당 행렬의 레이어 수를 나타냅니다. 각 레이어마다 다른 심볼을 사용합시다 :
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 .
. . . . . . .
행렬의 너비와 높이를 1 씩 증가시키는 것이 항상 레이어 수를 증가시키는 것은 아닙니다. 위의 행렬을 취하고 레이어와 치수를 표로하면 너비와 높이가 2 증가 할 때마다 레이어 수가 한 번 증가합니다.
+-----+--------+
| 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 |
+-----+--------+------------------+
NxN 행렬이 주어지면 회전해야하는 레이어 수를 프로그래밍 방식으로 어떻게 결정할 수 있습니까? 너비 또는 높이를 2로 나누고 나머지를 무시하면 다음과 같은 결과가 나타납니다.
+-----+--------+------------------+---------+
| 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 매트릭스에는 총 3 개의 레이어와 회전이 필요한 2 개의 레이어가 있습니다.
. . . . .
. 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 | . . . . . |
+-----+-----------+
너비와 높이가 동일하기 때문에 항상 그렇습니다. 따라서 레이어의 열 및 행 위치를 4 개가 아닌 2 개의 값으로 정의 할 수 있습니다.
두 번째 레이어로 안쪽으로 이동하면 열의 위치는 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 | . . . . . |
+-----+-----------+
따라서 행렬의 레이어를 탐색 할 수 있습니다. 이제 레이어 내에서 탐색하는 방법이 필요하므로 해당 레이어 주위로 요소를 이동할 수 있습니다. 요소는 한 레이어에서 다른 레이어로 ‘점프’하지는 않지만 각 레이어 내에서 이동합니다.
레이어에서 각 요소를 회전하면 전체 레이어가 회전합니다. 행렬의 모든 레이어를 회전하면 전체 행렬이 회전합니다. 이 문장은 매우 중요하므로 계속 진행하기 전에 이해하기 위해 최선을 다하십시오.
이제 요소를 실제로 이동시키는 방법, 즉 각 요소를 회전 한 다음 레이어와 궁극적으로 행렬을 회전시키는 방법이 필요합니다. 간단하게하기 위해 회전 가능한 레이어가 하나 인 3×3 매트릭스로 되돌립니다.
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변수와 오프셋을 사용하여 레이어 내에서 탐색합니다. 이 새로운 루프를 ‘요소 루프’라고합니다. 요소 루프는 맨 위 행, 각 요소는 오른쪽 아래, 각 요소는 맨 아래 행, 각 요소는 왼쪽 위를 따라 각 요소를 방문합니다.
- 맨 위 행을 따라 앞으로 이동하려면 열 인덱스를 증가시켜야합니다.
- 오른쪽으로 이동하면 행 색인이 증가해야합니다.
- 아래쪽을 따라 뒤로 이동하면 열 인덱스가 감소해야합니다.
- 왼쪽으로 이동하면 행 인덱스가 감소해야합니다.
이것은 복잡하게 들리지만, 위의 목표를 달성하기 위해 증가 및 감소하는 횟수는 매트릭스의 4면 모두에서 동일하게 유지되기 때문에 쉬워졌습니다. 예를 들면 다음과 같습니다.
- 맨 위 행을 가로 질러 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 = list(zip(*original[::-1]))시계 반대 방향으로 :
rotated_ccw = list(zip(*original))[::-1]작동 원리 :
zip(*original)목록에서 해당 목록을 새 목록으로 쌓아 2D 배열의 축을 교체합니다. ( *연산자 는 포함 된 목록을 인수로 분배하도록 함수에 지시합니다)
>>> list(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;
}
}답변
여기에는 좋은 코드가 많이 있지만 기하학적으로 진행되는 것을 보여주기 위해 코드 논리를 조금 더 잘 이해할 수 있습니다. 여기에 내가 접근하는 방법이 있습니다.
우선, 이것을 매우 쉬운 전치와 혼동하지 마십시오.
기본 아이디어는 레이어로 취급하고 한 번에 한 레이어 씩 회전하는 것입니다.
우리에게 4×4가 있다고 말해
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
두 번째로 치우친 다이아몬드
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도 변경됩니다. 생성자를 약간 변경하면 새 배열을 만들고 값을 복사하여 정렬합니다.
