題目描述

您將會得到一個維度為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矩陣旋轉的過程如下:

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

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

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

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

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

範例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次之後會儲存的值。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final int m = sc.nextInt(), n = sc.nextInt(), r = sc.nextInt();
        final int[][] a = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = sc.nextInt();
            }
        }
        final int[][] b = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                final int level = Math.min(Math.min(i, j), Math.min(m - i - 1, n - j - 1));
                final int mm = m - level * 2, nn = n - level * 2;
                if (mm == 1 || nn == 1) {
                    b[i][j] = a[i][j];
                } else {
                    int x = i, y = j;
                    final int s = (mm + nn) * 2 - 4;
                    final int left = level;
                    final int right = n - level - 1;
                    final int top = level;
                    final int bottom = m - level - 1;
                    final int rr = r % s;
                    for (int k = 1; k <= rr; ++k) {
                        if (y == left && x != bottom) {
                            ++x;
                        } else if (x == bottom && y != right) {
                            ++y;
                        } else if (y == right && x != top) {
                            --x;
                        } else if (x == top && y != left) {
                            --y;
                        } else {
                            throw new RuntimeException(i + ", " + j);
                        }
                    }
                    b[x][y] = a[i][j];
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                System.out.print(b[i][j]);
                if (j != n - 1) {
                    System.out.print(' ');
                }
            }
            System.out.println();
        }
    }
}