Rotate the matrix n times

Question

I was solving problems at HackerRank when I was stuck with this.

Problem Statement

You are given a two-dimensional matrix a, dimension MxN and a positive integer R. You need to rotate the matrix R times and print the resulting matrix. The rotation should be counterclockwise.

The rotation of the 4x5 matrix is ​​shown in the following figure. Please note that in one revolution you should only move elements one step (for clarity, see Test Examples).

It is guaranteed that the minimum of M and N will be even.

entrance

The first line contains three integers, separated by a space, M, N and R, where M is the number of rows, N is the number of columns in the matrix, and R is the number of times to be rotated. This is followed by the line M, where each line contains N spaces, separated by positive integers. These M-rows are a matrix.

Output

Print the rotated matrix.

Limitations

2 <= M, N <= 300 1 <= R <= 10^9 min(M, N) % 2 == 0 1 <= aij <= 108, where i ∈ [1..M] & j ∈ [1..N]' 

What I was trying to do was save circles in a 1D array. Something like that.

  while(true) { k = 0; for(int j = left; j <= right; ++j) {temp[k] = a[top][j]; ++k;} top++; if(top > down || left > right) break; for(int i = top; i <= down; ++i) {temp[k] = a[i][right]; ++k;} right--; if(top > down || left > right) break; for(int j = right; j >= left; --j) {temp[k] = a[down][j] ; ++k;} down--; if(top > down || left > right) break; for(int i = down; i >= top; --i) {temp[k] = a[i][left]; ++k;} left++; if(top > down || left > right) break; } 

Then I could easily rotate the 1D matrix by calculating its length modulo R. But then how can I return it in matrix form? Using a loop can again result in a timeout.

Please do not provide a code, but give only suggestions. I want to do it myself.

Created solution:

 #include <iostream> using namespace std; int main() { int m,n,r; cin>>m>>n>>r; int a[300][300]; for(int i = 0 ; i < m ; ++i){ for(int j = 0; j < n ; ++j) cin>>a[i][j]; } int left = 0; int right = n-1; int top = 0; int down = m-1; int tleft = 0; int tright = n-1; int ttop = 0; int tdown = m-1; int b[300][300]; int k,size; int temp[1200]; while(true){ k=0; for(int i = left; i <= right ; ++i) { temp[k] = a[top][i]; // cout<<temp[k]<<" "; ++k; } ++top; if(top > down || left > right) break; for(int i = top; i <= down ; ++i) { temp[k]=a[i][right]; // cout<<temp[k]<<" "; ++k; } --right; if(top > down || left > right) break; for(int i = right; i >= left ; --i) { temp[k] = a[down][i]; // cout<<temp[k]<<" "; ++k; } --down; if(top > down || left > right) break; for(int i = down; i >= top ; --i) { temp[k] = a[i][left]; // cout<<temp[k]<<" "; ++k; } ++left; if(top > down || left > right) break; //________________________________\\ size = k; k=0; // cout<<size<<endl; for(int i = tleft; i <= tright ; ++i) { b[ttop][i] = temp[(k + (r%size))%size]; // cout<<(k + (r%size))%size<<" "; // int index = (k + (r%size))%size; // cout<<index; ++k; } ++ttop; for(int i = ttop; i <= tdown ; ++i) { b[i][tright]=temp[(k + (r%size))%size]; ++k; } --tright; for(int i = tright; i >= tleft ; --i) { b[tdown][i] = temp[(k + (r%size))%size]; ++k; } --tdown; for(int i = tdown; i >= ttop ; --i) { b[i][tleft] = temp[(k + (r%size))%size]; ++k; } ++tleft; } size=k; k=0; if(top != ttop){ for(int i = tleft; i <= tright ; ++i) { b[ttop][i] = temp[(k + (r%size))%size]; ++k; } ++ttop; } if(right!=tright){ for(int i = ttop; i <= tdown ; ++i) { b[i][tright]=temp[(k + (r%size))%size]; ++k; } --tright; } if(down!=tdown){ for(int i = tright; i >= tleft ; --i) { b[tdown][i] = temp[(k + (r%size))%size]; ++k; } --tdown; } if(left!=tleft){ for(int i = tdown; i >= ttop ; --i) { b[i][tleft] = temp[(k + (r%size))%size]; ++k; } ++tleft; } for(int i = 0 ; i < m ;++i){ for(int j = 0 ; j < n ;++j) cout<<b[i][j]<<" "; cout<<endl; } return 0; } 

Answer 1

You need to break down this problem (remind me of the interview question from gg and fb):

• First decide to rotate the sequence of one position.
• Then enable rotation of the sequence N times
• Model each “circle” or ring as an array. In fact, you may or may not need to store separate data.
• Iterate over each ring and apply the rotating algorithm

Let's look at the case of an array of length L to rotate R Note that if R is a multiple of L , the array will not change. Also observe that turning x times to the right is the same as turning L - x left (and vice versa).

• Thus, you can first design an algorithm that can rotate once either left or right in one position.
• Reduce the problem of turning R times left by turning R modulo L left
• If you want to further reduce the problem of turning R modulo L left by turning left R modulo L or turning right L - R modulo L This means that if you have 100 elements and you need to make 99 turns to the left, you better make 1 turn to the right and do it.

Thus, the complexity will be equal to O (Number of circles x Lap length x Single rotation cost)

With an array in place, this means O( min(N,m) * (N * M)^2 )

If you use a doubly linked list as a temporary storage, one rotation sequence is performed by removing the front and placing it in the tail (or vice versa to rotate to the right). So what you can do is first copy all the data into a linked list. Run the single rotation algorithm R modulo L times, copy the linked list to the position of the ring and go to the next on the right until all the rings are processed.

• Copy ring data to the list O(L), L <= N*M
• The cost of one rotation is O (1)
• All rotations of R modulo L are O(L)
• Repeat on all min(N,m) rings

With a spare double linked list, this means O( min(N,m) * (N * M)) complexity

Answer 2

I would start with a simplifying assumption: M is less than or equal to N. Thus, you are guaranteed an even number of rows. (What if M> N? Then transpose the matrix, execute the algorithm and transpose the matrix again.)

Since you have an even number of rows, you can easily find the angles of each cycle inside the matrix. The outermost cycle has the following angles:

a _1,1 → a _{M, 1} → a _{M, N} → a <sub> 1, Nsub>

To find the next loop, move each corner inward, which means incrementing or decreasing the index in each corner, if necessary.

Knowing the sequence of angles, you can iterate over each cycle and save the values ​​in a one-dimensional vector. In each such vector a start with the index R % a.size() and increase the index a.size() - 1 time to iterate over the rotating elements of the loop. Copy each element a[i % a.size()] back into the loop.

Note that we do not actually rotate the vector. We perform a rotation starting at the offset index when we copy the elements back into the matrix. Thus, the total operating time of the O (MN) algorithm is optimal, since it costs O (MN) to read the input matrix only.

Answer 3

I would see this as a problem that divides the matrix into sub-matrices. You could probably write a function that will offset the outer and column matrices (and submatrices) each time you call it. Be careful to process the four corners of the matrix.

Check this box for suggestions on how to move columns.

Edit (more):

Read each circle of the matrix as a vector, use std :: rotate on it R% length.vector times, write back. Maximum 150 operations.

Answer 4

Each element moves unambiguously in accordance with one of four formulas, adding five movements of known sizes (I will leave the size calculation, since you wanted to figure it out):

 formula (one of these four): left + down + right + up + left down + right + up + left + down right + up + left + down + right up + left + down + right + up 

Since the smallest part of the matrix is ​​even, we know that there is no element remaining in place. After turning R element went around floor (R / formula) times, but still needs extra = R % formula shifts. Once you find out extra , just figure out the appropriate placement for the element.