c++ - 为递归函数传递什么来转换二维数组 "90 degrees"

Question

我想用递归来解决一道面试题:

"Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?"

我的想法是旋转“正方形”最外面的4个边，然后递归调用swap来旋转里面的“正方形”；但是，我很难弄清楚递归函数应该第一个传入的参数是什么(我把它标记为“？？？？”，我应该填什么？)

#include <iostream>
using namespace std;

const static int N = 4;

void swap(int** a, int length)
{
    if (length <= 1)
    {
        return;
    }

    int top[length];
    for (int i=0; i<length ; i++)
    {
        top[i] = a[0][i];
    }

    // left to top
    for (int i=0; i < length; i++)
    {
        a[0][i] = a[length-i-1][0];
    }

    // bottom to left
    for (int i=0; i < length; i++)
    {
        a[i][0] = a[length-1][i];
    }

    // right to bottom
    for (int i=0; i < length; i++)
    {
        a[length-1][i] = a[length-i-1][length-1];
    }

    // top to right
    for (int i=0; i < length; i++)
    {
        a[i][length-1]= top[i];
    }

    swap(????, length-2);
}

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

    int *b[N]; //surrogate
    for (size_t i=0;i<N; i++)
    {
        b[i] = a[i];
    }

    swap(b, N);
    return 0;
}

Answer 1

这是我的努力。计划是我们的旋转可以分解为仅旋转四个像素的组(通过考虑每次我们将正方形旋转 90 度时它映射到的位置，由一个像素组成的组)。

#include <iostream>
#include <iomanip>

template<typename PixelT, size_t N>
void rotate(PixelT (&pixel)[N][N], size_t shell = 0)
{
// end recursion condition
    if ( shell >= N / 2 )
        return;

// These variables will be optimized out, have written them here
// explicitly so it is clear what is going on. They represent the
// coordinate of those named sides of the square we are working on.
    auto top = shell;
    auto left = shell;
    auto bottom = (N-1) - shell;
    auto right = (N-1) - shell;

// For each pixel on the top side, rotate the four pixels 
// it maps to under 90 degree rotation
    for (auto i = 0; i < right - left; ++i)
    {
    // Anti-clockwise
        auto tmp = pixel[top][left+i];
        pixel[top][left+i] = pixel[top+i][right];
        pixel[top+i][right] = pixel[bottom][right-i];
        pixel[bottom][right-i] = pixel[bottom-i][left];
        pixel[bottom-i][left] = tmp;
    }

// Rotate next shell in
    rotate(pixel, shell + 1);
}

template<typename PixelT, size_t N>
void dump(PixelT (&pixel)[N][N])
{
    std::cout << "[\n";
    for (auto&& row : pixel)
    {
        for (auto&& pix : row)
            std::cout << std::setw(4) << pix;

        std::cout << '\n';
    }
    std::cout << "]\n";
}

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

    dump(a);
    rotate(a);
    dump(a);
}

递归的使用有点似是而非，因为递归参数可以用单行 for 循环替换。

同样，我实际使用的 foor 循环也可以用递归代替(因此我们对每个四像素集递归一次)