Rotate Array 5
Time limit1sMemory limit512 MB
Apply up to 2 million flip, rotate, and quadrant-shift operations to an N by M grid and print the final grid.
- Level
Medium5 of 10
- Topics
- Simulation, Implementation, Matrix, Math
- Solved
- No attempts yet
Problem
Given an array of size N×M, we want to apply operations to it R times. There are 6 operations in total.
Operation 1 flips the array upside down.
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 left to right.
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 to the right.
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 to the left.
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>
Operations 5 and 6 require splitting the array into 4 subarrays of size N/2×M/2. The figure below shows a 6×8 array divided 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 in 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 in 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 array size N, M and the number of operations R to perform.
From the second line, N lines give the elements Aij of array A.
The last line gives the operations to perform. The operations are separated by spaces, are the operation numbers described in the problem, and must be applied in order.
Output
Print the result of performing the R operations in order on the given array.
Constraints
- 2 ≤ N, M ≤ 100
- 1 ≤ R ≤ 2,000,000
- N and M are even
- 1 ≤ Aij ≤ 10^8