Hello, what is the algorithm for the rotation matrix of different dimensions 90 clockwise and counterclockwise. Additional memory is trivial, but without, and different dimensions ...

A dynamic array of dimension m x n.

This code works for dimension n x n:

As you can realize, rotate dynamic array (matrix), without extra memory?

A dynamic array of dimension m x n.

This code works for dimension n x n:

```
int tmp;
for(int i=0;i<n/2;i++)
{
for(int j=i;j<n-1-i;j++)
{
tmp = matr[i][j];
matr[i][j] = matr[n-j-1][i];
matr[n-j-1][i] = matr[n-i-1][n-j-1];
matr[n-i-1][n-j-1] = matr[j][n-i-1];
matr[j][n-i-1] = tmp;
}
}
}
```

As you can realize, rotate dynamic array (matrix), without extra memory?

asked April 7th 20 at 11:03

4 answers

answered on April 7th 20 at 11:05

Swap of cells using the sum and subtraction.

answered on April 7th 20 at 11:07

As you can realize, rotate dynamic array (matrix), without extra memory?

Something like this:

```
#include <stddef.h>
#include <stdio.h>
typedef int T;
void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
{
size_t i, j, k;
for (i = 0; i < m * n; ++i) {
T tmp0, tmp1;
for (j = 0; j < i; ++j) {
for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
}
if (k == i)
break;
}
if (j < i)
continue;
tmp0 = p[i];
for (j = turn(m, n, i); ; j = turn(m, n, j)) {
tmp1 = p[j];
p[j] = tmp0;
tmp0 = tmp1;
if (j == i)
break;
}
}
}
void dump(size_t m, size_t n, T p[m][n])
{
size_t i, j;
for (i = 0; i < m; ++i)
for (j = 0; j < n; ++j)
printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
}
turn_ccw size_t(size_t m, size_t n, size_t idx)
{
return (n - 1 - idx % n) * m + (idx / n);
}
turn_cw size_t(size_t m, size_t n, size_t idx)
{
return (idx % n) * m + m - 1 - (idx / n);
}
#define M 5
#define N 7
int main()
{
size_t i, j;
T a[M][N];
for (i = 0; i < M; ++i)
for (j = 0; j < N; ++j)
a[i][j] = i * N + j;
rotate(&a[0][0], M, N, turn_ccw);
dump(N, M, (T (*)[M])&a[0][0]);
printf("\n");
rotate(&a[0][0], N, M, turn_cw);
dump(M, N, (T (*)[N])&a[0][0]);
}
```

`turn`

converts the linear index of the element from the original array to the index of the element in the rotated array.The for loop moves i chain elements appear in each other since the beginning of the element i. The first cycle j determines whether element i already rearranged in the earlier part of the chain. The second for loop j moves one chain.

answered on April 7th 20 at 11:09

First and foremost, consider the option of saving the flag "transpose" and the account of the flag algorithms. Moreover, it will speed up the work TWICE, because the bypass on the column, the transposed matrix is physically a bypass line, which has a positive effect on the caching of the data matrix.

answered on April 7th 20 at 11:11

This rectangular "sausage" does not rotate. And store the vector of Westerners rotated. And to overload the index operator to access behaved according to the rules of affine transformations.

Find more questions by tags CC++Algorithms