Как заполнить 2D массив по диагонали на основе координат

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 и т. д.).

Наконец, да, я знаю, что этот вопрос похож на заданный здесь , здесь и здесь , но решения, описанные только тампройти и не заполнять матрицу.

Answer 1

Интересная проблема, если вы ограничены в прохождении массива строка за строкой. Я разделил прямоугольник на три области. верхний левый треугольник , нижний правый треугольник и ромб в середине .

Для верхнего левого треугольника значения в первом столбце (x = 0) могут быть рассчитаны с использованием общего арифметического ряда 1 + 2 + 3 + .. + n = n*(n+1)/2. Поля в этом треугольнике с одним и тем же значением x + y имеют одинаковую диагональ, и там это значение равно сумме из первого столбца + x.

Тот же подход работает для нижнего правого треугольника . Но вместо x и y используются w-x и h-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--;
    }
}

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++;
  }
}

Answer 3

В матрице 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

Это не окончательно, но оно должно дать вам кое-что для работы. Обратите внимание, что для начала вам нужно только значение предыдущего элемента в каждой строке и несколько начальных значений.

Answer 4

Если вам нужна простая функция, вы можете использовать рекурсивное определение.

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 )   [integer division, with no remainder/decimal]

И отработайте свою функцию оттуда.

---

В качестве альтернативы, если вы хотите использовать метод исключительно заполнение массивами по строкам без рекурсии, вы можете следовать следующим правилам:

1. Если вы находитесь в первой ячейке строки, «запомните» элемент в ячейке (R-1) (где R - ваша текущая строка) первой строки и добавьте к нему 1.
2. В противном случае просто добавьте H в ячейку, которую вы рассчитывали в последний раз (т. Е. В ячейку слева от вас).

Psuedo-Code: (Предполагается, что массив проиндексирован 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

Answer 5

Выполните шаги в 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++;
}