C++：以对角线方式处理2D数组元素

Question

假设我们有一个二维数组arr[N][N]，其中N是一个常数整数。假定arr的每个元素都被初始化。

如何使用嵌套的for循环按反对角线打印arr的元素？

我的意思是：

• 在最外层循环的第一次迭代之后，将打印arr[0][0]
• 在最外层循环的第二次迭代之后，将打印arr[0][1]和arr[1][0]
• 在最外层循环的第三次迭代之后，将打印arr[0][2]、arr[1][1]和arr[2][0]
• ...
• 在最外层循环的最后一次迭代之后，将打印arr[N-1][N-1]。

谢谢您的时间！

- Demi

---

哈哈，确实这个问题的表述有点像作业题，但其实并不是 ;) - Demi

JPEG的ZZ扫描遍历？ - Gary Tsui

Answer 1

对于所有写下“第二部分应该相似”的人，我很抱歉...它并不相似。

无论如何，这里是翻译的内容：

// traverse array diagonally
int c, tmp, x;
for (c = N - 1; c > -N; c--) {
    tmp = N - abs(c) - 1;
    x = tmp;
    while (x >= 0) {
        if (c >= 0) {
            std::cout << arr[x][tmp - x] << ", ";
        }
        else {
            std::cout << arr[N - (tmp - x) - 1][(N-1)-x] << ", ";
        }
        --x;
    }
    std::cout << "\n";
}

你需要这个是为了游戏或者其他什么吗？

[编辑] 再次观察，我认为我的回答写得不太好。下面是一个快速的运行过程：

假设N是3。

我们需要进行坐标组合的迭代，看起来像这样：

(0, 0)
(1, 0), (0, 1)
(2, 0), (1, 1), (0, 2)
(2, 1), (1, 2)
(2, 2)

首先是一些占位符：

int c,    // a counter, set by the outer loop
    tmp,  // for intermediate results
    x;    // the x-index into *arr* (*y* will be defined implicitly)

现在这个外层循环。

for (c = N - 1; c > -N; c--) { 

使 c 迭代 {2, 1, 0, -1, 2}。

下一步

    tmp = N - abs(c) - 1;
    x = tmp;

将{2, 1, 0, -1, -2}转换为{0, 1, 2, 1, 0}，这些数字是在此步骤中所需输出的长度减一（以便用作索引）。我们制作两份副本，tmp和x。

现在我们从x倒数到0：

    while (x >= 0) {
        ...
        --x;
    }

如果我们在arr的左上半部分，由c >= 0表示，那么对于arr中的x索引，需要从对角线开始向下到零(0到0，1到0和2到0)，而y索引需要从零开始向上到对角线(0到0，0到1和0到2)：

        if (c >= 0) {
            std::cout << arr[x][tmp - x] << ", ";
        }

一旦我们处于右下半部分，x-索引需要从N开始并向下到对角线(2到1和2到2)，而y-索引需要从对角线开始并上升到N(1到2和2到2)：

        else {
            std::cout << arr[N - (tmp - x) - 1][(N-1)-x] << ", ";
        }

最后，我们只需要在每行末尾添加一个换行符即可：

    std::cout << "\n";

明白了吗？:-)

- HumanCatfood

---

感谢您给我一个完整的答案 ;). 我需要这个，因为有一个嵌套的for循环，由于数据依赖性，无法按行或列并行化，所以只能按反对角线方向完成。 - Demi

好的？听起来有点吓人 :-)如果这对您有效，请点击“接受”好吗？谢谢!! :-) - HumanCatfood

Answer 2

这将适用于矩阵的一半..另一半将是类似的：

for (j = 0 ; j < N ; j++)
{
   for (i = 0 ; i <= j ; i ++)
   {
      printf("%d \n",a[i,j-i]);
   }
}

- Yochai Timmer

Answer 3

您可以注意到，对于任何对角线，两个“相邻”的元素由[x] [y]和[x + 1] [y-1]给出：也就是说，您向右上方对角线步进一步。

因此，您可以设置一个循环来设置对角线的第一个单元格。您只需要迭代所有y值，从[0] [y]开始，然后进行这个向右上方（对角线）的步骤，直到击中顶部或右侧。然后，您将需要通过从[0] [N-1]移动到[N-1] [N-1]来覆盖第二半部分。

代码如下：

for (int _y = 0; _y < N; _y++) {
    int x = 0, y = _y;
    while (x < N && y >= 0) {
        cout << arr[x][y];
        x++; y--;
    }

    cout << endl; // don't forget a newline
}

我将省略代码的后半部分，因为它应该是相同的。

- evgeny

---

+1 是为了表达赞同，尽管我更喜欢其他答案中的代码。 - Jitse Niesen

Answer 4

这里是一段Java代码片段，但算法是相同的

for(int i = 0; i < 10; i++){
    for(int j = 0; j <= i; j++){
        System.out.print(a[j][i-j] + " ");
    }
    System.out.println();
}

- user658991

Answer 5

看起来像这样：

for(row = 0; row < N; row++){  
   for(j = 0; j <= row; j++){  
      print Array[row - j][j];  
   }  
   newline;  
}  

- Toaster

Answer 6

这是矩阵两半部分的解决方案：

    //First half (including middle diagonal)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            print array[j][i - j];
        }
        newline;
    }

    //Second half (excluding middle diagonal)
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            print array[n - i + j][n - j - 1];
        }
        newline;
    }

- Squidcor

Answer 7

这里是我认为有用的一个解决方案 R是总行数。

    void diagonalOrder(int arr[][COLS],int R)
    {

        for (int i = 0; i < R+COLS-1; i++)
        {
            int col;
            int row;
            i<COLS?col=i:col=(COLS-1);
            col>i?row=col-i:row=i-col;

            for(int j=col;j>=0 ;j--)
            {
                if(row<R)
                    cout<<arr[row][j]<<" ";
                row++;
            }
            cout<<endl;
        }
    }

ie.
const int ROWS = 4;
const int COLS = 3;

int arr[][COLS] = {{ 1, 2, 4 },
                        { 3, 5, 7},
                        { 6, 8, 10},
                        { 9, 11, 12}
                    };
    diagonalOrder(arr,ROWS);

Output
----------
1
2 3
4 5 6
7 8 9
10 11
12

------------------------------------------------------
const int ROWS = 8;
const int COLS = 3;

    int arr8[][COLS] = {{ 1, 2, 4 },
                        { 3, 5, 7 },
                        { 6, 8, 10 },
                        { 9, 11, 13 },
                        { 12, 14, 16},
                        { 15 ,17, 19},
                        { 18 ,20, 22},
                        { 21, 23, 24}

                    };

    cout<<"\n\n8*3 Matrix"<<endl<<endl;
    diagonalOrder(arr8,8);

--------------------------------------------------------------
Output
--------------------------------------------------------------
1
2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23
24
-----------------------------------------

    int arr[][COLS] = {{ 1, 2, 4 ,20},
                        { 3, 5, 7,20},
                        { 6, 8, 10,20},
                        { 9, 11, 12,20}
                    };
-------------------------------------------------------------
Output
-------------------------------------------------------------

1
2 3
4 5 6
20 7 8 9
20 10 11
20 12
20


You can work with n*n Matrix ..

- Pravin Tukadiya