Как повернуть матрицу на одну позицию по часовой стрелке?

Question

[MiT]

Задача:
Поворот матрицы. Сдвинуть элементы заданной матрицы в пределах периметра каждых вложенных подматриц на одну позицию по часовой стрелке. Матрица N*M
Вопрос:
Как это сделать? Именно поворот на одну позицию, а также не забыть про подматрицу.

Разъяснение условия

Пример (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;
}

Answer 1

[res2001]

Быстрее всего это можно сделать создав второй массив и копируя туда элементы в нужном порядке.
Если же непременно нужно "на месте", то есть стандартный алгоритм std::rotate, или можно воспользоваться советом от сюда. Берите вариант с reversе.

Comments

[MiT]

Быстрее всего это можно сделать создав второй массив и копируя туда элементы в нужном порядке.

Примерно покажите как это сделать(желательно с двухмерным массивом)

[res2001]

MiT_73, Честно говоря, я не допонял вашего вопроса и привел ответы для циклического сдвига массива. Но у вас немного другая история, вот решение.
Писал на Си, т.к. мне он сейчас ближе.

[MiT]

res2001, можно сделать ещё что-то типо этого)

spoiler

Вот, примерно так (есть куча мест для оптимизации, упрощений и обобщений. Например, брать начальные значения размеров непосредственно из матрицы. Я заморачиваться не стал...):

{
    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;
    }
}

Answer 2

[tsarevfs]

Функции очень помогут вам разбить задачу на более простые части.

///Повернуть рамку на 1 позицию
///\param top номер строки левого верхнего угла рамки в исходной матрице
///\param left номер колонки левого верхнего угла рамки в исходной матрице
///\param width ширина рамки (количество колонок)
///\param width height высота рамки (количество строк)
///         left
///          | w
///       ************
///  top--***abcdef***
///      h***n****g***
///       ***mlkjih***
///       ************
///
/// rotateFrame(matrix, 1, 3, 6, 3)
void rotateFrame(int **matrix, int top, int left, int width, int height)
{
    if (width == 1)
    {
        int copyOfLast = shiftColumn(matrix, top, left, height, true);
        matrix[top][left] = copyOfLast
        return;
    }

    if (height == 1)
    {
        int copyOfLast = shiftRow(matrix, top, left, width, true);
        matrix[top][left] = copyOfLast
        return;
    }

    //верхняя строка
    int copyOfLast = shiftRow(matrix, top, left, width, true);
    
    //левый столбец
    shiftColumn(matrix, top, left, height, false);

    //нижняя строка
    shiftRow(matrix, top + height  - 1, left, width, false);

    //правый столбец
    shiftColumn(matrix, top, left + width - 1, height, true);

    //восстанавливаем элемент из правого верхнего угла
    matrix[top + 1][left + width - 1] = copyOfLast;
}

///Сдвинуть участок строки длинной length на одну позицию в лево или право в зависимости от shiftLeft.
///Первый элемент не изменяется, последний пропадает.
///Возвращает элемент, который будет утрачен.

///   **abcd** -> **aabc** (shiftLeft == true), возвращаем d
///   **abcd** -> **bcdd** (shiftLeft == false), возвращаем a
int shiftRow(int **matrix, int top, int left, int length, bool shiftLeft)
{

}

///Аналогично shiftRow, но для столбца
int shiftColumn(int **matrix, int top, int left, int length, bool shiftDown)
{

}

Comments

[tsarevfs]

Собственно поворот матрицы будет заключаться в вызове rotateFrame для каждой "рамки" в вашей матрице.

[MiT]

tsarevfs, а можно пример на основание моего кода?