有人可以在我的矩阵旋转代码中找到错误吗？

Question

我正在尝试进行 hackerrank 矩阵旋转挑战。我的代码在某个地方有一个我找不到的错误。该代码应该将测试矩阵的所有外部和内部循环旋转 r 次（1 <= r <= 10 E 9）。如果我不对 r 做模数，代码运行良好，除了 r 的较高值，它在 hackerrank 服务器上超时。如果我对 r 进行取模，那么代码将无法通过 r >= (r % number_of _elements_in_outer_loop) 的测试用例。我找不到错误。提前感谢您的任何回复。以下是代码（在 Visual Studio 2015 年测试）。具有要求的 hackerrank 挑战是 here

// MatrixRotation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
//  int i, j, k;
    int m, n, r;
    int rotations, rot;
    int m_start, m_end, m_len;
    int n_start, n_end, n_len;
    int m_curr, n_curr;

//-------------------------------------------------------------------------
// For hackerrank testing
//-------------------------------------------------------------------------

    int i, j;

    for (i = 1; i <= 3; i++)
    {

        if (i == 1) std::cin >> m;
        else if (i == 2) std::cin >> n;
        else std::cin >> r;

    }

    int **matrix = new int*[m];
    for (int i = 0; i < m; ++i) {
        matrix[i] = new int[n];
    }

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            std::cin >> matrix[i][j];


    //-------------------------------------------------------------------------
    // For local machine in Visual Studio testing
    //-------------------------------------------------------------------------

    /*

    int i, j, k;

    m = 10;
    n = 8;
    r = 40;

    int **matrix = new int*[m];
    for (int i = 0; i < m; ++i) {
        matrix[i] = new int[n];
    }

    k = 1;
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            matrix[i][j] = k;
            k += 1;
        }

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            std::cout << matrix[i][j] << " ";

            if (j == n - 1)
                std::cout << endl;

        }

    std::cout << endl;

    */

    //-------------------------------------------------------------------------
    // Begin computations
    //-------------------------------------------------------------------------

    int outer_loop_rotation;

    outer_loop_rotation = (n - 1)  + (m - 1) + (n - 1) + (m - 1)  ;

    rot = r % outer_loop_rotation;

//  std::cout << endl << endl << "outer loop rotation = " << outer_loop_rotation << endl << endl << "rot = " << rot << endl << endl;

    for (rotations = 1; rotations <= rot; rotations++)
    {

        m_start = 0;
        m_end = m - 1;

        n_start = 0;
        n_end = n - 1;

        m_len = m_end - m_start;
        n_len = n_end - n_start;


        // Following while loop is 1 rotation for all loops

        while (m_len >= 1 && n_len >= 1)
        {

            int loop_start = matrix[m_start][n_start];

            // Following for loop is for row start

            m_curr = m_start;
            n_curr = n_start;

            for (i = 1; i <= n_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr][n_curr + 1];
                n_curr += 1;

            }

            // Following for loop is for col end

            m_curr = m_start;
            n_curr = n_end;

            for (i = 1; i <= m_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr + 1][n_curr];
                m_curr += 1;

            }

            // Following for loop is for row end

            m_curr = m_end;
            n_curr = n_end;

            for (i = 1; i <= n_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr][n_curr - 1];
                n_curr -= 1;

            }

            // Following for loop is for col start

            m_curr = m_end;
            n_curr = n_start;

            for (i = 1; i <= m_len   ; i++)
            {
                if (i < m_len )
                {
                    matrix[m_curr][n_curr] = matrix[m_curr - 1][n_curr];
                    m_curr -= 1;


                }

                else
                {

                    matrix[m_curr][n_curr] = loop_start;


                }

            }

            m_start += 1;
            m_end -= 1;

            n_start += 1;
            n_end -= 1;

            m_len = m_end - m_start;
            n_len = n_end - n_start;


        } // End while loop

    } // End for loop

    // End computations, now output to command line

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            std::cout << matrix[i][j] << " ";

            if (j == n - 1)
                std::cout << endl;

        }


    return 0;
}

Answer 1

我认为错误是你对整个矩阵只计算一次模值，对应于旋转最外层的循环重复长度。但是，矩阵中的每一层都将具有不同的循环长度。比如最外层的循环周期长度，你计算的是：

(n - 1)  + (m - 1) + (n - 1) + (m - 1)

然而，对于倒数第二层，重复长度为：

(n - 3)  + (m - 3) + (n - 3) + (m - 3)

或更普遍

((n - ((layer*2)+1))  + (m - ((layer*2)+1))) * 2

其中最外层为 0，倒数第二层为 1，依此类推

因此，您需要更改代码来计算每一层的模数，而不是一次计算整个矩阵的模数。

Answer 2

如果有人感兴趣，这是有效的最终代码。

  // MatrixRotation.cpp : Defines the entry point for the console application.
  //

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
//  int i, j, k;
    int m, n, r;
    int rotations, rot;
    int loop_decrement, loop_rotation;
    int m_start, m_end, m_len;
    int n_start, n_end, n_len;
    int m_curr, n_curr;

//-------------------------------------------------------------------------
// For hackerrank testing
//-------------------------------------------------------------------------

    int i, j;

    for (i = 1; i <= 3; i++)
    {

        if (i == 1) std::cin >> m;
        else if (i == 2) std::cin >> n;
        else std::cin >> r;

    }

    int **matrix = new int*[m];
    for (int i = 0; i < m; ++i) {
        matrix[i] = new int[n];
    }

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            std::cin >> matrix[i][j];


    //-------------------------------------------------------------------------
    // For local machine in Visual Studio testing
    //-------------------------------------------------------------------------

/*  

    int i, j, k;

    m = 4;
    n = 4;
    r = 2;

    int **matrix = new int*[m];
    for (int i = 0; i < m; ++i) {
        matrix[i] = new int[n];
    }

    k = 1;
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            matrix[i][j] = k;
            k += 1;
        }

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            std::cout << matrix[i][j] << " ";

            if (j == n - 1)
                std::cout << endl;

        }

    std::cout << endl;

    */

    //-------------------------------------------------------------------------
    // Begin computations
    //-------------------------------------------------------------------------

    m_start = 0;
    m_end = m - 1;

    n_start = 0;
    n_end = n - 1;

    m_len = m_end - m_start;
    n_len = n_end - n_start;


    // Following while loop is all rotations
    // for all loops one loop at a time

    loop_decrement = 1;

    while (m_len >= 1 && n_len >= 1)
    {
        // loop_rotation = number of items in current loop

        loop_rotation = (n - loop_decrement) + (m - loop_decrement) + (n - loop_decrement) + (m - loop_decrement);

        rot = r % loop_rotation;

        for (rotations = 1; rotations <= rot; rotations++)
        {

            int loop_start = matrix[m_start][n_start];

            // Following for loop is for top row in current loop

            m_curr = m_start;
            n_curr = n_start;

            for (i = 1; i <= n_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr][n_curr + 1];
                n_curr += 1;

            }

            // Following for loop is for right col in current loop

            m_curr = m_start;
            n_curr = n_end;

            for (i = 1; i <= m_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr + 1][n_curr];
                m_curr += 1;

            }

            // Following for loop is for bottom row in current loop

            m_curr = m_end;
            n_curr = n_end;

            for (i = 1; i <= n_len  ; i++)
            {

                matrix[m_curr][n_curr] = matrix[m_curr][n_curr - 1];
                n_curr -= 1;

            }

            // Following for loop is for left col in current loop

            m_curr = m_end;
            n_curr = n_start;

            for (i = 1; i <= m_len   ; i++)
            {
                if (i < m_len )
                {
                    matrix[m_curr][n_curr] = matrix[m_curr - 1][n_curr];
                    m_curr -= 1;


                }

                else
                {

                    matrix[m_curr][n_curr] = loop_start;


                }

            }

        } // End for loop

        m_start += 1;
        m_end -= 1;

        n_start += 1;
        n_end -= 1;

        m_len = m_end - m_start;
        n_len = n_end - n_start;

        loop_decrement += 2;

    } // End while loop

    // End computations, now output to command line

    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
        {
            std::cout << matrix[i][j] << " ";

            if (j == n - 1)
                std::cout << endl;

        }


    return 0;
}

有人可以在我的矩阵旋转代码中找到错误吗？

Can someone find the bug in my code for Matrix Rotation?

c++

algorithm

matrix

visual-c++