c++ - 顺时针旋转M*N矩阵90度,C++

Question

我正在尝试旋转字符 vector 的 vector 。

我做了一个二维 vector 矩阵设置。现在矩阵从文件中获取输入，我使用 vector.push_back(c) 将字符添加到 vvc；vvc 数组的一个例子是这样的

aaaaa
azzza
azaza
azzza
azaaa
azaaa
azaaa
aaaaa

我有 vvc 设置，但我想将它旋转 90 度。我逆时针旋转了 90 度，但我需要顺时针旋转 90 度。

截至目前，我的代码执行此操作

90 counter clock
aaaaaaaa
azzzzzza
azazaaaa
azzzaaaa
aaaaaaaa

它通过这个循环完成；

cout <<"\n90 counter clock"<<endl;
    for (size_t colNo = 0; colNo < kvsize2; colNo++)
    {
        for (const auto &row : twovector)
        {
            char colVal = row.at(colNo);
            cout << colVal;
        }
        cout << endl;
    }

我只是在学习 vector ，以及 vector 的范围。尝试做一个递减循环几乎可以工作，但总是让我陷入段错误。

“已解决”我在用

twovector.push_back(temp);

使用

twovector.insert(twovector.begin(),temp);

给我

90 计数器时钟
啊啊啊啊
阿兹兹扎
啊啊啊啊
啊啊啊
aaaaaaaa

Answer 1

解决问题的特定部分:

If anyone has any tips or suggestions on how to rotate a M*N 2d vector array

C++ 擅长将算法与数据分离。

请注意，答案有点冗长，并且是以教程为目的编写的。
让我们开始吧!

我们需要 rotate_2d_matrix_clockwise 算法的 3 个特征:

• 它应该适用于所有数据类型，即 int、char、double 或任何用户定义的类型。
• 它应该适用于不同类型的容器，例如 std::array 和 std::vector
• 它应该是可链接的，即用户应该能够在 rotate_2d_matrix_clockwise 返回的结果上调用 rotate_2d_matrix_clockwise，以实现 2 次旋转。

一旦我们明确了我们的要求，我们就可以为我们的算法起草一些用例。

std::vector<std::vector<char>> data = { {'a', 'b', 'c', 'd'}, 
                                        {'e', 'f', 'g', 'h'}, 
                                        {'i', 'j', 'k', 'l'} };
rotate_2d_matrix_clockwise(data); // rotating 2d-matrix of vector<char>

std::array<std::array<int, 4>, 3> data2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
// rotating 2d-matrix of array<int>, twice
rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data2))); 

所以让我们使用一些模板来创建一个通用的 2d-clockwise-rotate 函数。

我们的rotate_2d_matrix_clockwise 将:

• 获取original_matrix 并返回一个新的rotated_matrix。
• 自动推断传递给它的容器的尺寸，即 M x N。
• 创建 rotated_matrix 并将其传递给辅助函数 rotate_2d_matrix_clockwise_impl，实际工作将在其中完成。

那么 std::array 的 rotate_2d_matrix_clockwise 的实现会是什么样子呢？

template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
    -> std::array<std::array<T, N>, M>
{
    std::array<std::array<T, N>, M> rotated_matrix;
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
    return rotated_matrix;
}

整洁而精确。
不过，std::vector 的 rotate_2d_matrix_clockwise 实现有点困惑。

template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
    int const M = original_matrix[0].size(); // deduce M and N
    int const N = original_matrix.size();

    Matrix2D rotated_matrix; // vector has no form, hence we have to resize it for `N x M`
    rotated_matrix.resize(M);
    for (auto x = 0; x < M; ++x) {
        rotated_matrix[x].resize(N);
    }

    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N); // rotate
    return rotated_matrix;
}

现在让我们看看实际的旋转算法 rotate_2d_matrix_clockwise_impl 会是什么样子。
应该注意，该算法独立于容器和/或包含的数据。它只专注于旋转。

template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & original_matrix,
                                     RotatedMatrix2D        & rotated_matrix,
                                     int              const M,
                                     int              const N)
{
    for (auto x = 0; x < N; ++x) {
        for (auto y = 0; y < M; ++y) {
            // Source : https://stackoverflow.com/questions/4780119/2d-euclidean-vector-rotations
            rotated_matrix[y][-x -1 +N] = original_matrix[x][y];
        }
    }
}

这是一个用 C++11 编译的完整工作示例。

#include <iostream>
#include <vector>
#include <array>

template<typename Matrix2D>
void print_matrix(Matrix2D const & vec)
{
    std::cout << "size of matrix is [" << vec[0].size() << " x " << vec.size() << "]\n";
    for (auto const & inner_vec : vec) {
        for (auto const & item : inner_vec) {
            std::cout << item << ", ";
        }
        std::cout << std::endl;
    }
}

template<typename OriginalMatrix2D, typename RotatedMatrix2D>
void rotate_2d_matrix_clockwise_impl(OriginalMatrix2D const & matrix,
                                     RotatedMatrix2D        & rotated_matrix,
                                     int              const M,
                                     int              const N)
{
    for (auto x = 0; x < N; ++x) {
        for (auto y = 0; y < M; ++y) {
            // Source : https://stackoverflow.com/questions/4780119/2d-euclidean-vector-rotations
            rotated_matrix[y][-x -1 +N] = matrix[x][y];
        }
    }
}

template<typename T, size_t M, size_t N>
auto rotate_2d_matrix_clockwise(std::array<std::array<T, M>, N> const & original_matrix)
    -> std::array<std::array<T, N>, M>
{
    std::array<std::array<T, N>, M> rotated_matrix;
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
    return rotated_matrix;
}

template<typename Matrix2D>
auto rotate_2d_matrix_clockwise(Matrix2D const & original_matrix) -> Matrix2D
{
    int const M = original_matrix[0].size();
    int const N = original_matrix.size();
    Matrix2D rotated_matrix;
    rotated_matrix.resize(M);
    for (auto x = 0; x < M; ++x) {
        rotated_matrix[x].resize(N);
    }
    rotate_2d_matrix_clockwise_impl(original_matrix, rotated_matrix, M, N);
    return rotated_matrix;
}


int main()
{
    std::array<std::array<int, 4>, 3> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    std::cout << "\nBefore Rotation :\n";
    print_matrix(data);
    std::cout << "\nAfter 2nd Clockwise Rotation :\n";
    print_matrix(rotate_2d_matrix_clockwise(rotate_2d_matrix_clockwise(data)));

    std::vector<std::vector<char>> data2 = { {'a', 'b', 'c', 'd'}, {'e', 'f', 'g', 'h'}, {'i', 'j', 'k', 'l'}};
    std::cout << "Before Rotation :\n";
    print_matrix(data2);
    std::cout << "\nAfter Clockwise Rotation :\n";
    print_matrix(rotate_2d_matrix_clockwise(data2));

    return 0;
}