c++ - 用连续数字 C++ 填充二维数组之字形

Question

我坚持这个。你能帮帮我吗？

编写一个初始化二维数组的函数。数组是一个正方形
矩阵(即它的宽度和高度相同。)数组应该在之字形风格。具体来说，我们从左上角开始往下，放一个
数字从1开始。一旦触底，我们转到下一列并填写
从下到上的数字。第三行我们向下填数字
列，在第四列向上，依此类推。当所有的过程结束数组中的元素被填充。

However, How do I get my output like this?
1 10 11 20 21
2 9 12 19 22
3 8 13 18 23
4 7 14 17 24
5 6 15 16 25

#include <iomanip>
#include <iostream>
using namespace std;
const int SIZE = 5; // Note SIZE can be anything between 1 to 9
void initGrid(int grid[SIZE][SIZE]);
void printGrid(int grid[SIZE][SIZE]);
int main() {
    int grid[SIZE][SIZE];
    initGrid(grid);
    printGrid(grid);
}
void initGrid(int grid[SIZE][SIZE]) {
    int inc = 1;
    for (int j = 0; j < SIZE; j++) {
        for (int i = 0; i < SIZE; i++) {
             grid[i][j] = inc;
             inc++;
        }
    }
}
void printGrid(int grid[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            // setw() function handles the printing format.
            cout << setw(2) << grid[i][j] << " ";
        }
        cout << endl;
    }
}

Answer 1

网格每两列采用相同的填充方式，奇数列从小到大依次填充，偶数列从大到小依次填充。您所要做的就是将其转换为代码:

template<size_t Rows, size_t Cols>
void initGrid(int (&grid)[Rows][Cols]) {
    int value = 1;
    for (size_t j = 0; j < Cols; ++j) {
        // first fill the odd column in descending order
        for (size_t i = 0; i < Rows; ++i, ++value) {
            grid[i][j] = value;
        }
        // then, if there is one, fill the even column
        ++j;
        if (j == Cols )
            break;
        for (size_t i = Rows; i > 0; ++value) {
            --i;   // size_t is unsigned, so I have to check i before decrementing
            grid[i][j] = value;
        }
    }
}

我使用与您使用的相同的数据结构(但函数签名不同)只是为了专注于算法，但我会改用类。

如果您不想按列遍历数组(对于 大 数组，可能会由于缓存未命中而导致性能下降)，您可以计算每一行中值之间的差异:

template<size_t Rows, size_t Cols>
void zig_zag_fill(int (&grid)[Rows][Cols])
{
    int diff_up = 1;
    int diff_down = Rows * 2 - 1;
    for (size_t i = 0; i < Rows; ++i, diff_down -= 2, diff_up += 2)
    {
        int value = i + 1;
        size_t j = 0;
        while ( j < Cols )
        {
            grid[i][j] = value;
            value += diff_down;
            ++j;
            if ( j == Cols )
                break;
            grid[i][j] = value;
            value += diff_up;
            ++j;
        }
    }
}

一个完整的测试程序是这样的:

#include <iostream>
#include <iomanip>

template<size_t Rows, size_t Cols>
void zig_zag_fill(int (&grid)[Rows][Cols]);

template<size_t Rows, size_t Cols>
void printGrid(int (&grid)[Rows][Cols]);

int main() {
    int grid[5][6];
    zig_zag_fill(grid);
    printGrid(grid);
    std::cout << '\n';
    int grid2[6][5];
    zig_zag_fill(grid2);
    printGrid(grid2);
    std::cout << '\n';
    int grid3[5][5];
    zig_zag_fill(grid3);
    printGrid(grid3);
    std::cout << '\n';
    int grid4[6][6];
    zig_zag_fill(grid4);
    printGrid(grid4);
    std::cout << '\n';
}

template<size_t Rows, size_t Cols>
void initGrid(int (&grid)[Rows][Cols]) {
    int value = 1;
    for (size_t j = 0; j < Cols; ++j) {
        for (size_t i = 0; i < Rows; ++i, ++value) {
            grid[i][j] = value;
        }
        ++j;
        if (j == Cols )
            break;
        for (size_t i = Rows; i > 0; ++value) {
            --i;
            grid[i][j] = value;
        }
    }
}

template<size_t Rows, size_t Cols>
void zig_zag_fill(int (&grid)[Rows][Cols])
{
    int diff_up = 1;
    int diff_down = Rows * 2 - 1;
    for (size_t i = 0; i < Rows; ++i, diff_down -= 2, diff_up += 2)
    {
        int value = i + 1;
        size_t j = 0;
        while ( j < Cols )
        {
            grid[i][j] = value;
            value += diff_down;
            ++j;
            if ( j == Cols )
                break;
            grid[i][j] = value;
            value += diff_up;
            ++j;
        }
    }
}


template<size_t Rows, size_t Cols>
void printGrid(int (&grid)[Rows][Cols]) {
    for (size_t i = 0; i < Rows; ++i) {
        for (size_t j = 0; j < Cols; ++j) {
            std::cout << std::setw(2) << grid[i][j] << " ";
        }
        std::cout << '\n';
    }
}

会输出:

 1 10 11 20 21 30  2  9 12 19 22 29  3  8 13 18 23 28  4  7 14 17 24 27  5  6 15 16 25 26  1 12 13 24 25  2 11 14 23 26  3 10 15 22 27  4  9 16 21 28  5  8 17 20 29  6  7 18 19 30  1 10 11 20 21  2  9 12 19 22  3  8 13 18 23  4  7 14 17 24  5  6 15 16 25  1 12 13 24 25 36  2 11 14 23 26 35  3 10 15 22 27 34  4  9 16 21 28 33  5  8 17 20 29 32  6  7 18 19 30 31