Поиск по ячейкам в таблице?

Question

[svarnoi420]

Например, есть таблица вида:
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
Тоже все хорошо.
Но он ломается, когда я на рэндом таблицу выдаю. Бесконечно крутиться.
Все же надо реализовать так , чтобы сначала на рэндом только два минуса расставлялись в ненулевые, а потом уже плюсы.

Comments

[Виталий Витренко]

Вы пытаетесь транспортную задачу решить? Если да, то там таблицы должны быть не просто рандомные, а удовлетворять определенным условиям.

[svarnoi420]

Виталий Витренко: да, транспортную задача. Условию соблюдены. Сумма у поставщиков равна сумме потребителей, т.е. закрытого типа задача.

Answer 1

[svarnoi420]

решил вопрос