Например, есть таблица вида:
3 0 0 7
0 4 0 0
0 0 5 6
Нужно построить замкнутый контур (цикл). Должен получиться некий квадрат (прямоугольник), грубо говоря.
Алгоритм, по идее, следующий:
Находим две любые ячейки с ненулевой нагрузкой (обязательно в разных строках и столбцах) и даем им знак "-". Из них будут вычитаться значения (значение минимальное из двух ячеек - 3).
Чтобы замкнуть контур, выбираем еще две ячейки (неважно, со значениями или пустые), которые составят прямоугольник с предыдущими двумя и даем им знак "+". Им прибавляем значение (то есть тоже минимальное число - 3).
В итоге должно получится, к примеру, так:
-3 0 0 +7
0 4 0 0
+0 0 5 -6
После манипуляций:
0 0 0 10
0 4 0 0
3 0 5 3
Я пробовал по другому алгоритму (реализация на Java если что, просто первая песочница, которая в голову пришла):
jsfiddle.net/bn55ftca
Итог:
-3 +0 0 7
+0 -4 0 0
0 0 5 6
Тоже все хорошо.
Но он ломается, когда я на рэндом таблицу выдаю. Бесконечно крутиться.
Все же надо реализовать так , чтобы сначала на рэндом только два минуса расставлялись в ненулевые, а потом уже плюсы.
Простой
