Rotate matrix in 90º

Navigation
5

I need to create an algorithm in C to rotate a 10x10 matrix by 90 degrees, though I can not use an auxiliary array for that.

Simplifying what was asked to try to find some pattern and use it to solve the problem I used a 3x3 array and compared the position that each element occupies in the original array and that will occupy in the rotated array. 

ORIGINAL     | ROTACIONADA
0x0 0x1 0x2  | 0x2 1x2 2x2
1x0 1x1 1x2  | 0x1 1x1 2x1
2x0 2x1 2x2  | 0x0 1x0 2x0

You can see a pattern in which for the original matrix the value of the line remains constant for each cycle of 3 positions and the value of the column is increased by 1 in this same cycle. For the rotated version of the array the row and column values respectively correspond to the column and row. Although I do not know how to take advantage of this information, since transferring the values to the positions corresponding to the rotated version will lose values that I will still use. For example:
Transferring the value from 0X0 to 2X0 will lose the original 2x0 content that you would need to transfer to 2x2 later.

    
asked by anonymous 24.08.2015 / 15:53

3 answers

4

To change the value of 2 variables it is usual to use a temporary variable. 

// troca a e b
int tmp = a;
a = b;
b = tmp;

In your case of running the array, you have to do the same thing with 4 variables 

// roda 4 variaveis
int tmp = a;
a = b;
b = c;
c = d;
d = tmp;

Now the problem is to select the variables!

But it's not hard to figure out which elements should run for each of the 5x5 sub-array elements from top left.

The element in mat[0][0] must run with mat[9][0] , mat[9][9] , and mat[0][9] .

The element in mat[1][3] must run with mat[3][8] , mat[8][6] , and mat[6][1] .

The element in mat[row][col] must run with mat[col][10 - row - 1] , mat[10 - row - 1][10 - col - 1] , and mat[10 - col - 1][row] .

Note: The algorithm has nothing to do with C.

    
25.08.2015 / 14:00
4

The simplest way to do this is to rotate on the screen when printing. For a 3x3 array of integers, i are the rows and j are the columns, you can display it "tumbled" like this: 

for(j = 2; j >= 0; j--)       
{
        for(i = 0; i < 3; i++)
        {
               printf("%d      ", mat[i][j]);
        }
        printf("%c", 10);
}

In this way you print, from right to left, columns as if they were lines, "spinning" your matrix by 90 degrees.

    
25.08.2015 / 12:56
1

In addition to @DaviAragao's response, you may want to save the array to it and rotate more than once, well following the pattern to rotate an array with an auxiliary variable:

Each element of the array always varies between 4 positions (would be equivalent to, in radians, 0, pi, pi / 2 and 3 * pi / 2), when it completes the cycle, it returns to the starting position. This can be seen in the following image:

Thisobeysrotaterules,whichyoumustsubtractfromN(whereNisthesizeinthearray,incaseCwouldbeN-1)thevalueoftheelementcolumn(whichincaseCwillstartfrom0)andinvertrowwithcolumn.Theorderyousettheseoperationswilldefinethedirectioninwhichthearrayisrotated:

  • Changerowandcolumnandthensubtract=Clockwise
  • Subtractandthenswaplineandcolumn=Counterclockwise(sameasimage)

Insummaryyouwillhavethefollowingmeta-algorithm(thisforasquarematrixNxNandclockwiserotation):

para i = 0, i < N/2 e i = i + 1: para j = 0, j < N/2 e j = j + 1: original = matriz[i][j] linha = i coluna = j para l = 0, l < 3 e l = l + 1: se l % 2 = 0: matriz[linha][coluna] = matriz[linha][N-coluna] senao: matriz[linha][coluna] = matriz[N-linha][coluna] fimse aux = linha linha = coluna coluna = N-aux fimpara matriz[linha][coluna] = original fimpara fimpara

This algorithm is for clockwise rotation; for counterclockwise it is enough to change the order of the auxiliary variable and the line. It is worth remembering that the complexity of this algorithm is O (n²), perhaps there is a better way to solve this problem.

    
25.08.2015 / 14:49
How do I exit a loop by entering a specific value? Is there any way to know if I've done git push?