Нахождение индексов уникальных строк и столбцов в двумерном массиве и минимальной суммы элементов в этих позициях - PullRequest
Новая
       15

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

0 голосов
/ 19 апреля 2020

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

В качестве примера приведены 3 контрольных примера.

Контрольный пример 1: 

{
{5, 4, 4, 1, 6},
{1, 3, 2, 4, 6},
{3, 2, 3, 2, 6},
{0, 4, 5, 4, 6},
(6, 6, 6, 6, 6}
};

Output: (3,0) (2,1) (1,2) (0,3) (4,4)
Minimum sum: 11

Контрольный пример 2: 

{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};

Output: (0,0) (1,1) (2,2) (3,3) (4,4)
Minimum sum: 0

Тестовый пример 3: 

{
{1, 2, 3, 4, 5},
{5, 4, 3, 2, 1},
{1, 2, 7, 4, 5},
{5, 4, 3, 2, 1},
{1, 2, 3, 4, 5},
};

Output: (0,0) (2,1) (4,2) (1,3) (3,4)
Minimum sum: 9

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

1 Ответ

0 голосов
/ 19 апреля 2020

Уникальная строка и столбец означает, что никакие два элемента не разделяют строку или столбец.

Здесь я выделил выбранные числа.

Вы можете видеть это, когда выбрано число , Другой номер в этом же столбце также не выбран. Никакой другой номер в этой же строке не выбран.

5 4 4 1 6
1 3 2 4 6
3 2 3 2 6
0 4 5 4 6
6 6 6 6 6 

1 + 2 + 2 + 0 + 6 = 11
...