在不使用新阵列的情况下就地旋转2D阵列 - 最佳C++解决方案？

Question

我的一个学生问我用C++数组做这种功课.这对我来说似乎很有意思,所以,虽然我已经解决了这个问题,但我想与你分享我的解决方案并了解其他变体和意见.问题如下:

问题 给出2D动态二次矩阵(数组)A(nxn).需要通过90度逆时针到阵列转动,也就是说,旋转A [1,1]字段之后应包含A [1,n]和A的值[1,n]的字段应包含的值A [N,N-].并且还需要在解决此问题时不要使用任何其他数组.

我 告诉学生我的解决方案是执行以下操作(将示意性地表示步骤):
我建议定义一个类,作为其成员,将具有2D数组.并且当用户将请求A [i,j] 一时,定义将在A [j,n + 1-i]元素上返回引用的操作.用两个词我建议为数组创建一个包装器,并通过包装器通过数组进行操作.

Answer 1

维基百科有一篇关于就地矩阵转置的文章.

考虑:

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

因此,在进行转置后,将行反转,您可以轻松地就地执行这些行.

Answer 2

您可以使用"四向交换"和带有一些旋转魔法的嵌套循环(在纸上制作):

template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
    T x(a);
    a = b;
    b = c;
    c = d;
    d = x;
}

template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
    const size_t d = dim-1;
    for (size_t y = 0; y < dim/2; ++y)
    {
        for (size_t x = y; x < d-y; ++x)
        {
            swap(matrix[y  ][x  ],
                 matrix[x  ][d-y],
                 matrix[d-y][d-x],
                 matrix[d-x][y  ]);
        }
    }
}

测试程序:

template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
    for (size_t y = 0; y < dim; ++y)
    {
        for (size_t x = 0; x < dim; ++x)
        {
            std::cout << matrix[y][x] << ' ';
        }
        std::cout << '\n';
    }
}

int main()
{
    int matrix[4][4] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    rotate(matrix);
    print(matrix);
}

输出:

4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

现在你只需要将它从模板形式转换为动态形式;)