[HackerRank]矩陣旋轉(Matrix Rotation)


題目描述

您將會得到一個維度為MxN的二維矩陣a,和一個整數R。您必須要旋轉這個矩陣R次,然後輸出矩陣的結果。旋轉方向為逆時針。

假設有一個4x5的矩陣如下:

11 12 13 14 15
21 22 23 24 25
31 32 33 34 35
41 42 43 44 45

旋轉時,會將外圈和內圈各自逆時針旋轉。旋轉一次後的結果如下:

12 13 14 15 25
11 23 24 34 35
21 22 32 33 45
31 41 42 43 44

原題網址

https://www.hackerrank.com/challenges/matrix-rotation-algo

輸入格式

第一行包含三個用空格分隔的整數M、N和R。M是矩陣的列數,N是矩陣的行數,M和N中的最小值必為偶數。R是矩陣旋轉的次數,為正整數。

接下來的M行都各有N個整數,表示MxN矩陣,數值都在1到108之間。

輸出格式

輸出旋轉之後的矩陣。
Print the rotated matrix.

範例輸入1

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

範例輸出1

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15

範例輸入2

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

範例輸出2

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

範例輸入3

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

範例輸出3

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

範例輸入4

2 2 3
1 1
1 1

範例輸出4

1 1
1 1

額外解釋

範例1矩陣旋轉的過程如下:

範例2矩陣旋轉的過程如下:

範例3矩陣旋轉的過程如下:

範例4的矩陣內容都相同,不管怎麼旋轉都一樣是原本的內容。

解題概念

為求程式效能,我們並不需要實際的將矩陣旋轉。但我們需要事先知道,矩陣中的每層(圈)數字,旋轉一圈的次數分別是多少。

要如何知道矩陣中的每層數字旋轉一圈的次數為多少呢?從最外層開始往內來看,最外層是第0層,接著是第1層、第2層,一直到最後一層。

這裡要先想辦法知道某個矩陣元素的位置是在(i,j),那麼這個元素是位在第幾層呢?試想一下,(0,0)在第0層、(1,1)在第1層、(2,2)在第2層,假設這個矩陣為6x6,則(0,5)和(5,0)和(5,5)也是在第0層、(4,4)和(4,1)和(1,4)也是在第1層、(3,3)和(3,2)和(2,3)也是在第2層。這其中有什麼規律嗎?有,那就是元素的位置或是其正斜對角線鏡射位置(這兩個位置必定在同一層上)的最小值,就是元素的所在層數。以(4,3)來舉例,正斜對角線鏡射的位置在(0,1),最小值是0,因此(4,3)在第0層。

知道怎麼計算元素的所在層數之後,接著要計算該層元素正好轉一圈的旋轉次數為多少次,才可以用餘數運算避免掉該層元素轉了一圈以上的情形。

讓一層元素正好轉一圈的旋轉次數,即為該層元素數量。至於元素數量要如何計算,要先算出該層所形成的矩形之兩相鄰邊的元素數量。若矩陣大小為MxN,第l層矩形的兩相鄰邊MM和NN計算方式如下:

MM = M - (l * 2)
NN = N - (l * 2)

若MM和NN其中一邊等於1,那麼元素數量即為MM和NN的最大值。否則為周長減4,即:

(MM + NN) * 2 - 4

減4是要減掉重複計算的4個角。

算出元素數量後,即可計算旋轉次數R除上元素數量的餘數,就是真正需要旋轉的次數RR。

接著只要走訪每個元素位置,並模擬每次的旋轉,計算出旋轉RR次之後元素的位置在哪即可。由於是逆時針旋轉,當目前模擬的位置(x,y)是在矩形左邊時,x要加1;當目前模擬的位置(x,y)是在矩形下邊時,y要加1;當目前模擬的位置(x,y)是在矩形右邊時,x要減1;當目前模擬的位置(x,y)是在矩形上邊時,y要減1。最後(x,y)所對應的矩陣元素,即為原本位置(i,j),旋轉R次或是RR次之後會儲存的值。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章