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 - находится на пересечении).
мне кажется, со вторым будет несколько проще работать. как считаешь?
в общем, попробуй... если что получится - выкладывай. если нет - напиши об этом...
Сообщение отредактировано: мисс_граффити -
--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует. На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!