主页 / 问题 / 761369
Accepted
MiT
Asked:2020-12-21 17:10:52 +0000 UTC2020-12-21 17:10:52 +0000 UTC

如何将矩阵顺时针旋转一位？(C++)

  • 772

任务： 矩阵旋转。在每个嵌套子矩阵的周长内将给定矩阵的元素顺时针移动一个位置。矩阵NxM。

问： 怎么办？它是一个位置的旋转，也不要忘记子矩阵。

条件说明

Пример (N=3; M=4):
0| 1 | 2 | 3 | 4 
=|================
1| 1   2   3   4  
2| 5   6   7   8  
3| 9   10  11  12

Результат (Как видите 6 и 7 поменяли свое местоположение в своей подматрице, так как матрица 3х4):
0| 1 | 2 | 3 | 4 
=|================
1| 5   1   2   3  
2| 9   7*  6*  4  
3| 10  11  12  8

Пример №2 (N=4; M=4):
0| 1 | 2 | 3 | 4 
=|================
1| 1   2   3   4  
2| 5   6   7   8  
3| 9   10  11  12
4| 13  14  15  16

Результат №2 (Как видите 6, 7, 10, 11 тоже повернулись на один элемент вправо):
0| 1 | 2 | 3 | 4 
=|================
1| 5   1   2   3  
2| 9   10* 6*  4  
3| 13  11* 7*  8
4| 14  15  16  12

"Цифра"* для пояснения

我尝试了一个一维数组，但得出的结论是子矩阵很难组装。 我要考虑的代码：

int main() {
int i, j;
int N;

cout << "Введите размеры матрицы:" << endl;
cout << "N = ";
cin >> N;
cout << "Матрица размером: " << N << "x" << N << endl;
//ДА, я знаю что матрица у меня N на N. Позже она станет размером N на M

int o = N * N;
int k = 0, mas[o];

int **A = new int *[N];
for (i = 0; i < N; i++) {
    A[i] = new int[N];
}

int **B = new int *[N];
for (i = 0; i < N; i++) {
    B[i] = new int[N];
}
cout << "Введите матрицу:" << endl;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        cin >> A[i][j];
    }
}
cout << "Матрица до поворота:" << endl;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        B[i][j] = A[i][j];
        cout << B[i][j] << " ";
    }
    cout << endl;
}
//Тут и нужно сделать поворот матрицы
/*Test*/
cout << "Одномерная матрица:" << endl;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        mas[k++] = B[i][j];
    }
}
for (k = 0; k < o; k++) {
    cout << mas[k] << " ";
}
cout << endl;

cout << "Сортировка:" << endl;
for (k = 0; k < o - 1; k++) {
    int temp = mas[k];
    mas[k] = mas[k + 1];
    mas[k + 1] = temp;
}
for (k = 0; k < o; k++) {
    cout << mas[k] << " ";
}
cout << endl;

k = 0;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        B[i][j] = mas[k++];
    }
}
/*Test*/

cout << "Матрица после поворота:" << endl;
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        cout << B[i][j] << " ";
    }
    cout << endl;
}
for (i = 0; i < N; i++) {
    delete[] A[i];
    delete[] B[i];
}
system("pause");
return 0;
}
c++

2 个回答

  1. Best Answer

    n x m我们需要旋转的矩阵中“环”的数量是

    inline unsigned ring_number(unsigned n, unsigned m)
{
  return (std::min(n, m) + 1) / 2;
}

    我们实现了一个迭代器，它将环号“视为”r元素的线性序列，从环的左上角元素开始逆时针进行（假设矩阵支持接口[i][j]）

    #include <cassert>
#include <utility>
#include <iterator>
#include <algorithm>

template <typename M> 
using RingIteratorBase = std::iterator<std::forward_iterator_tag, std::remove_reference_t<decltype((std::declval<M>()[0][0]))>>;

template <typename M> 
class RingIterator : public RingIteratorBase<M>
{
public:
  RingIterator() : 
      matrix(), r(), i(), n(), m(), 
      length(), y_side(), x_side()
    {}

  RingIterator(M &matrix, unsigned r, unsigned n, unsigned m) : 
    matrix(&matrix), r(r), i(0), n(n), m(m)
  { 
    assert(r < ring_number(n, m)); 
    assert(n > r * 2 && m > r * 2);
    y_side = n - r * 2;
    x_side = m - r * 2;
    length = y_side > 1 && x_side > 1 ? y_side * 2 + x_side * 2 - 4 : std::max(y_side, x_side);
  }

  RingIterator end()
  { 
    assert(matrix != nullptr);
    RingIterator it(*this);
    it.i = it.length;
    return it;
  }

  RingIterator operator ++()
  {
    assert(matrix != nullptr && i < length);
    ++i;
    return *this;
  }

  typename RingIteratorBase<M>::reference operator *() const
  {
    assert(matrix != nullptr && i < length);
    Ij ij = ring_index_to_ij();
    return (*matrix)[ij.i][ij.j];
  }

  friend bool operator ==(const RingIterator &lhs, const RingIterator &rhs)
  {
    assert(lhs.matrix == rhs.matrix && lhs.r == rhs.r && lhs.length == rhs.length);
    return lhs.i == rhs.i;
  }

  friend bool operator !=(const RingIterator &lhs, const RingIterator &rhs)
  {
    return !(lhs == rhs);
  }

private:
  M *matrix;
  unsigned r, i, n, m;
  unsigned length, y_side, x_side;

  struct Ij { unsigned i, j; };

  Ij ring_index_to_ij() const
  {
    assert(i < length);
    unsigned i_side = i;

    if (i_side < y_side)
      return { r + i_side, r }; 

    i_side -= y_side - 1;
    if (i_side < x_side)
      return { r + y_side - 1, r + i_side };

    i_side -= x_side - 1;
    if (i_side < y_side)
      return { r + y_side - 1 - i_side, r + x_side - 1 };

    i_side -= y_side - 1;
    return { r, r + x_side - 1 - i_side };
  }
};

    现在，使用这样的迭代器，您可以简单地使用标准算法std::rotate依次旋转矩阵的所有环

    #include <vector>
#include <iostream>
#include <iomanip>

int main()
{
  using Matrix = std::vector<std::vector<int>>;
  Matrix matrix =
  {
    {  1,  2,  3,  4 },
    {  5,  6,  7,  8 },
    {  9, 10, 11, 12 },
    { 13, 14, 15, 16 }
  };

  unsigned n = matrix.size(), m = matrix[0].size();

  for (const auto &row : matrix)
  {
    for (const auto &e : row)
      std::cout << std::setw(3) << e;
    std::cout << std::endl;
  }

  std::cout << std::endl;

  unsigned n_rings = ring_number(n, m);
  for (unsigned r = 0; r < n_rings; ++r)
  {
    RingIterator<Matrix> it_begin(matrix, r, n, m);
    std::rotate(it_begin, std::next(it_begin), it_begin.end());
  }

  for (const auto &row : matrix)
  {
    for (const auto &e : row)
      std::cout << std::setw(3) << e;
    std::cout << std::endl;
  }

  std::cout << std::endl;
}

    http://coliru.stacked-crooked.com/a/c5278f0ff20491d8

    • 3

  2. 这里，是这样的（优化、简化、泛化的地方很多。比如直接从矩阵中取维数的初值\u200b\u200b。我就懒得...）：

    template<typename Matrix>
void Rotate(Matrix&M,
            size_t rb, size_t re,
            size_t cb, size_t ce)
{
    if (rb == re)
    {
        if (cb < ce)
        {
            auto t = M[rb][ce];
            for(size_t i = ce; i >= cb+1; --i)
            {
                M[rb][i] = M[rb][i-1];
            }
            M[rb][cb] = t;
        }
        return;
    }
    if (cb == ce)
    {
        if (rb < re)
        {
            auto t = M[re][cb];
            for(size_t i = re; i >= rb+1; --i)
            {
                M[cb][i] = M[cb][i-1];
            }
            M[rb][cb] = t;
        }
        return;
    }
    auto t = M[rb+1][cb];
    for(size_t i = rb+1; i <= re - 1; ++i) M[i][cb]   = M[i+1][cb];
    for(size_t i = cb+1; i <= ce;     ++i) M[re][i-1] = M[re][i];
    for(size_t i = re-1; i >= rb;     --i) M[i+1][ce] = M[i][ce];
    for(size_t i = ce-1; i >= cb;     --i) M[rb][i+1] = M[rb][i];
    M[rb][cb] = t;
    ++rb; --re; ++cb; --ce;
    if (rb <= re && cb <= ce) Rotate(M,rb,re,cb,ce);
}

    使用开始和结束索引调用，例如

    int main(int argc, const char * argv[])
{
    int A[3][4] = { 1,2,3,4,5,6,7,8,9,10,11,12 };
    Rotate(A,0,2,0,3);
    for(int i = 0; i < 3; ++i)
    {
        for(int j = 0; j < 4; ++j)
        {
            cout << setw(5) << A[i][j];
        }
        cout << endl;
    }
}
    • 1

相关问题