Общий алгоритм ограничения размещения в матрице

Question

Я хочу разместить элементы в матрице n * n. Ограничение состоит в том, что на каждой диагонали допускается не более m элементов. Я не могу придумать общий способ выразить это ограничение. Кто-нибудь может помочь?

Спасибо.

Answer 1

Диагоналей (m = n-1):

0 1 2 . . . m
1 2 . . . m .
2 . . . m . .
. . . m . . .
. . m . . . .
. m . . . . .
m . . . . . 2m

Они могут быть представлены массивом, diag1 [2 * (n-1)].

Вот другое направление:

m . . . . . 2m
. m . . . . .
. . m . . . .
. . . m . . .
2 . . . m . .
1 2 . . . m .
0 1 2 . . . m

Они могут быть представлены аналогичным массивом, diag2 [2 * (n-1)].

Пример матрицы 5x5:

diag1 [2 * (n-1)] представляет следующие диагонали ...

0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8

diag2 [2 * (n-1)] представляет следующие диагонали ...

4 5 6 7 8
3 4 5 6 7
2 3 4 5 6
1 2 3 4 5
0 1 2 3 4

Оба этих массива и следующие функции должны быть добавлены в ваш матричный класс, при условии, что он у вас есть.

addElement(element_ *elementptr, int x, int y)
{
   if (diag1[x+y] < maxDiag1 && diag2[x+(n-1)-y] <maxDiag2) {
      diag1[x+y]++; 
      diag2[x+(n-1)-y]++;
      matrix[x][y] = elementptr;
   } else {
      // show error message?  return 0?  etc.
   }
}

remElement(int x, int y)
{
   if (matrix[x][y] != NULL) {
      diag1[x+y]--;
      diag2[x+(n-1)-y]--;
      matrix[x][y] = NULL;
   } else {
      // show error message?  return 0?  etc.
   }
}