Rotating an Array 3
InterviewTime limit2sMemory limit512 MB
Apply a sequence of up to 1000 operations (vertical flip, horizontal flip, quarter rotations, and quadrant swaps) to an N by M array and print the final arrangement.
- Level
Medium5 of 10
- Topics
- Implementation, Simulation, Matrix, Array
- Solved
- No attempts yet
Problem
Given an array of size N×M, apply R operations to it. There are 6 operations in total.
Operation 1 flips the array vertically.
1 6 2 9 8 4 → 4 2 9 3 1 8
7 2 6 9 8 2 → 9 2 3 6 1 5
1 8 3 4 2 9 → 7 4 6 2 3 1
7 4 6 2 3 1 → 1 8 3 4 2 9
9 2 3 6 1 5 → 7 2 6 9 8 2
4 2 9 3 1 8 → 1 6 2 9 8 4
<array> <result>
Operation 2 flips the array horizontally.
1 6 2 9 8 4 → 4 8 9 2 6 1
7 2 6 9 8 2 → 2 8 9 6 2 7
1 8 3 4 2 9 → 9 2 4 3 8 1
7 4 6 2 3 1 → 1 3 2 6 4 7
9 2 3 6 1 5 → 5 1 6 3 2 9
4 2 9 3 1 8 → 8 1 3 9 2 4
<array> <result>
Operation 3 rotates the array 90 degrees clockwise.
1 6 2 9 8 4 → 4 9 7 1 7 1
7 2 6 9 8 2 → 2 2 4 8 2 6
1 8 3 4 2 9 → 9 3 6 3 6 2
7 4 6 2 3 1 → 3 6 2 4 9 9
9 2 3 6 1 5 → 1 1 3 2 8 8
4 2 9 3 1 8 → 8 5 1 9 2 4
<array> <result>
Operation 4 rotates the array 90 degrees counterclockwise.
1 6 2 9 8 4 → 4 2 9 1 5 8
7 2 6 9 8 2 → 8 8 2 3 1 1
1 8 3 4 2 9 → 9 9 4 2 6 3
7 4 6 2 3 1 → 2 6 3 6 3 9
9 2 3 6 1 5 → 6 2 8 4 2 2
4 2 9 3 1 8 → 1 7 1 7 9 4
<array> <result>
To perform operations 5 and 6, split the array into 4 subarrays of size N/2×M/2. The picture below shows an array of size 6×8 split into 4 groups, labeled with the numbers 1 through 4.
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
4 4 4 4 3 3 3 3
4 4 4 4 3 3 3 3
4 4 4 4 3 3 3 3
Operation 5 moves the subarray of group 1 to the position of group 2, group 2 to group 3, group 3 to group 4, and group 4 to group 1.
3 2 6 3 1 2 9 7 → 2 1 3 8 3 2 6 3
9 7 8 2 1 4 5 3 → 1 3 2 8 9 7 8 2
5 9 2 1 9 6 1 8 → 4 5 1 9 5 9 2 1
2 1 3 8 6 3 9 2 → 6 3 9 2 1 2 9 7
1 3 2 8 7 9 2 1 → 7 9 2 1 1 4 5 3
4 5 1 9 8 2 1 3 → 8 2 1 3 9 6 1 8
<array> <result>
Operation 6 moves the subarray of group 1 to the position of group 4, group 4 to group 3, group 3 to group 2, and group 2 to group 1.
3 2 6 3 1 2 9 7 → 1 2 9 7 6 3 9 2
9 7 8 2 1 4 5 3 → 1 4 5 3 7 9 2 1
5 9 2 1 9 6 1 8 → 9 6 1 8 8 2 1 3
2 1 3 8 6 3 9 2 → 3 2 6 3 2 1 3 8
1 3 2 8 7 9 2 1 → 9 7 8 2 1 3 2 8
4 5 1 9 8 2 1 3 → 5 9 2 1 4 5 1 9
<array> <result>
Input
The first line gives the size of the array N, M and the number of operations to perform R.
Each of the next N lines gives an element Aij of array A.
The last line gives the operations to perform. The operations are separated by spaces and are the operation numbers described in the problem. They must be applied in order.
Output
Print the result of applying the R operations to the given array in order.
Constraints
- 2 ≤ N, M ≤ 100
- 1 ≤ R ≤ 1,000
- N and M are even
- 1 ≤ Aij ≤ 10^8