ansaurus

Question

How to rotate a N x N matrix by 90 degrees?

Answer 1

A:

You could create a second array and then copy the first one into the second one by reading row-major in the first one and writing column-major to the second one.

So you would copy:

1  2  3
4  5  6
7  8  9

and you would read the first row then write it back up starting like:

3
2
1

samoz 2010-05-23 19:31:06

Answer 2

+8 A:

for(int i=0; i<n/2; i++)
   for(int j=0; j<(n+1)/2; j++)
       cyclic_roll(a[i][j], a[n-1-j][i], a[n-1-i][n-1-j], a[j][n-1-i]);


void cyclic_roll(int &a, int &b, int &c, int &d)
{
   int temp = a;
   a = b;
   b = c;
   c = d;
   d = temp;
}

Note I haven't tested this, just compoosed now on the spot. Please test before doing anything with it.

Pavel Radzivilovsky 2010-05-23 19:32:55

could you explain on how did you come up with the indexes ?

Passionate programmer 2010-05-23 19:38:37

Explaining the indexes.. well, think where the location at (i,j) goes when rotating 90 degrees. Just imagine the picutre. (i,j)->(end-j, i). As high as the original was far from the left, and as far from the left as it was from the bottom of the matrix.

Pavel Radzivilovsky 2010-05-23 19:42:23

If one rotates counter-clockwise, the mapping is a[p][k] --> a[N-1-k][p] --> a[N-1-p][N-1-k] --> a[k][N-1-p]. I think there is also an error in the constrain for i. It should be i < n/2 in the for loop (for j it's ok). Look at the 3x3 example below. Number 4 gets taken care of, when rotating 2. You don't want to rotate for i = 1 and j = 0 again.

Maciej Hehl 2010-05-23 19:50:27

I can't edit. The code should befor(int i=0; i < N/2; i++) for(int j=0; j < (N+1)/2; j++) cyclic_roll(a[i][j], a[N-1-j][i], a[N-1-i][N-1-j], a[j][N-1-i]);

Maciej Hehl 2010-05-23 20:45:58

The third parameter to the cyclic_roll function still needs a correction. It Should be a[n-1-i][n-1-j] :)

Maciej Hehl 2010-05-23 21:38:53

thanks again, fixed

Pavel Radzivilovsky 2010-05-24 17:54:22

ansaurus

tags:

views:

answers:

How to rotate a N x N matrix by 90 degrees?

related questions