реализуемо ли Опции

[.helga]

Реализуемо ли это в Делфи??


1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными

[мисс_граффити]

в принципе, думала примерно так же.
единственное уточнение - надо будет параллельно анализировать строки и столбцы.
то есть как-то так: нашли самую "нулевую" строку, потом - самый "нулевый" столбец, и только после этого решаем, что вычеркивать.
и на следующем этапе уже вычеркнутые нули не принимать во внимание.

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

Цикл заканчивается, когда не осталось невычеркнутых нулей. То есть, если идем вторым путем, массив обнулился. Если первым - можно хранить кол-во оставшихся нулей в отдельной переменной.

следующий вопрос: как проверять, вычеркнуто ли то или иное число?
у меня есть 2 идеи:
1) создаем дополнительный массив, в который записываем номера вычеркнутых строк и столбцов.
2) исходный массив объявляем не так:

matr: array[1..m,1..m] of integer;

а так:

type
element=record
info,checked: integer;
end;
var matr: array[1..m,1..m] of element;

причем в поле info храним собственно значение (цифру), а в checked - информацию о зачеркнутости (0 - не зачеркнуто, 1 - зачеркнуто, 2 - находится на пересечении).

мне кажется, со вторым будет несколько проще работать.
как считаешь?

в общем, попробуй...
если что получится - выкладывай. если нет - напиши об этом...

Сообщение отредактировано: мисс_граффити - 2.01.2007 0:46