如何根据坐标对二维数组进行对角线填充

Question

我正在构建一个类似热图的矩形数组界面，我希望“热点”位置在数组的左上角，“冷点”位置在右下角。因此，我需要将数组对角线填充如下：

    0    1    2    3
  |----|----|----|----|
0 | 0  | 2  | 5  | 8  |
  |----|----|----|----|
1 | 1  | 4  | 7  | 10 |
  |----|----|----|----|
2 | 3  | 6  | 9  | 11 |
  |----|----|----|----|

所以，我需要一个函数f(x,y)，其满足以下要求：

f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11

（或者，当然，一个类似的函数f(n)，其中f(7)=10，f(9)=6等）。

最后，是的，我知道这个问题类似于在这里， 和，但那里描述的解决方案只遍历而不填充矩阵。

- hwschuur

---

只需遍历数组并将当前位置填充为当前步骤，是吗？ - Ozan

不，一个限制是数组按行从左到右遍历。这就是为什么我正在寻找一个计算每个值的函数，而不是以特定方式遍历数组的原因。 - hwschuur

那么你想直接计算f(x,y)，而不是填充一个数组吗？因为我看不出为什么数组需要从左到右填充。因为如果你像Ozan建议的那样填充一个数组，然后只需查询array[x][y]即可直接找到f(x,y)... - BlueRaja - Danny Pflughoeft

Answer 1

有趣的问题，如果您只能逐行遍历数组。我将矩形分为三个区域。左上角三角形，右下角三角形和中间的菱形。

对于左上角的三角形，第一列（x=0）中的值可以使用常见算术级数1 + 2 + 3 + .. + n = n *（n + 1）/ 2进行计算。具有相同x+y值的该三角形中的字段在同一对角线上，它们的值是来自第一列+x的总和。

相同的方法适用于右下角的三角形。但是，使用w-x和h-y而不是x和y，其中w是矩形的宽度，h是高度。该值必须从数组中最高值w*h-1中减去。

对于中间的菱形，有两种情况。如果矩形的宽度大于（或等于）高度，则矩形的左下角字段是菱形中最低值的字段，并且可以通过h-1之前的总和进行计算。从那里开始，您可以想象菱形是一个矩形，其x值为x+y，原始矩形的y值为y。因此，计算该新矩形中剩余值很容易。在另一种情况下，当高度大于宽度时，可以使用该算术总和计算位于x=w-1和y=0的字段，并且可以将菱形想象为x值为x，y值为y-(w-x-1)的矩形。

代码可以通过预先计算值进行优化。我认为还有一个适用于所有情况的公式。也许我以后会考虑它。

inline static int diagonalvalue(int x, int y, int w, int h) {
    if (h > x+y+1 && w > x+y+1) {
        // top/left triangle
        return ((x+y)*(x+y+1)/2) + x;
    } else if (y+x >= h && y+x >= w) {
        // bottom/right triangle
        return w*h - (((w-x-1)+(h-y-1))*((w-x-1)+(h-y-1)+1)/2) - (w-x-1) - 1;
    }

    // rhomboid in the middle
    if (w >= h) {
        return (h*(h+1)/2) + ((x+y+1)-h)*h - y - 1;
    }
    return (w*(w+1)/2) + ((x+y)-w)*w + x;
}

---

for (y=0; y<h; y++) {
    for (x=0; x<w; x++) {
        array[x][y] = diagonalvalue(x,y,w,h);
    }
}

当然，如果没有这样的限制，类似这样的东西应该会更快：

n = w*h;
x = 0;
y = 0;
for (i=0; i<n; i++) {
    array[x][y] = i;
    if (y <= 0 || x+1 >= w)  {
        y = x+y+1;
        if (y >= h) {
            x = (y-h)+1;
            y -= x;
        } else {
            x = 0;
        }
    } else {
        x++;
        y--;
    }
}

- rudi-moore

---

广泛的解释，做得好。确实，拥有一个适用于所有情况的公式会很优雅。另一种选择是通过后者“干净”的算法填充一个“参考数组”，然后在行/列约束算法中访问该数组的值。 - hwschuur

Answer 2

这个（使用 NxN 矩阵）怎么样？

count = 1;
for( int k = 0; k < 2*N-1; ++k ) {
  int max_i = std::min(k,N-1);
  int min_i = std::max(0,k-N+1);
  for( int i = max_i, j = min_i; i >= min_i; --i, ++j ) {
    M.at(i).at(j) = count++;
  }
}

- verkri

Answer 3

按照第三个示例中的步骤进行操作，这将提供索引（以便打印出切片），然后只需使用递增计数器设置值即可。

int x[3][3];
int n = 3;
int pos = 1;
for (int slice = 0; slice < 2 * n - 1; ++slice) {
    int z = slice < n ? 0 : slice - n + 1;
    for (int j = z; j <= slice - z; ++j)
        x[j][slice - j] = pos++;
}

- reece

Answer 4

在一个M*N矩阵中，当按照您提供的示例方式进行遍历时，值似乎会增加n，除了边界情况之外，因此

f(0,0)=0
f(1,0)=f(0,0)+2
f(2,0)=f(1,0)+3

...一直到f(N,0)。

f(0,1)=1
f(0,2)=3

然后

f(m,n)=f(m-1,n)+N, where m,n are index variables

并且

f(M,N)=f(M-1,N)+2, where M,N are the last indexes of the matrix

这并不是最终结论，但它应该能给你提供一些工作的线索。请注意，每行中只需要前一个元素的值以及一些起始值即可开始。

- Ozan

Answer 5

如果你想要一个简单的函数，你可以使用递归定义。

H = height

def get_point(x,y)
  if x == 0
      if y == 0
        return 0
      else
        return get_point(y-1,0)+1
      end
  else
    return get_point(x-1,y) + H
  end
end

这利用了任何值都是H+其左侧项目的价值的事实。 如果该项目已经位于最左边的列，则找到其远左上角的单元格，从那里向左移动并加1。

这是使用动态规划的好机会，可以“缓存”或记忆已经完成的函数。

---

如果你想让某件事情被 f(n) “严格”执行，你可以使用以下关系式：

n = ( n % W , n / H )   [整数除法，没有余数/小数]

从这里开始编写你的函数。

---

或者，如果您想要一种纯粹的按行填充数组的方法，而没有递归，您可以遵循以下规则：

1. 如果您在该行的第一个单元格上，“记住”第一行的(R-1)单元格中的项目（其中R是当前行），并将其加1。
2. 否则，只需将H添加到您最后计算的单元格（即，您左侧的单元格）。

伪代码：（假设数组由arr[row,column]索引）

arr[0,0] = 0

for R from 0 to H

  if R > 0
    arr[R,0] = arr[0,R-1] + 1 
  end

  for C from 1 to W

    arr[R,C] = arr[R,C-1]

  end

end

- Justin L.