Rotating an Array 2

Interview

Time limit1sMemory limit512 MB

Summary
Rotate each concentric layer of an N by M matrix one cell counterclockwise, R times, and print the final matrix.
Level

Medium5 of 10

Topics
Matrix, Simulation, Implementation, Array
Solved
No attempts yet

Problem

Given an array of size N×M, we want to rotate it counterclockwise. Each layer of the array shifts by one cell counterclockwise, as in the figure.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

For example, rotating the array below twice transforms it as follows.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <start>       <rot 1>       <rot 2>

Given an array and an integer R, find the result of rotating the array R times.

Input

The first line gives the size of the array N, M and the number of rotations R to perform.

The next N lines give the elements Aij of the array A.

Output

Output the result of rotating the given array R times.

Constraints

  • 2 ≤ N, M ≤ 300
  • 1 ≤ R ≤ 109
  • min(N, M) mod 2 = 0
  • 1 ≤ Aij ≤ 108

Examples3

  1. Example 1

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

  2. Example 2

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

  3. Example 3

    Input
    2 2 3
1 1
1 1
    Expected output
    1 1
1 1