1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице 2 Найти наименьший из элементов, через которые не проходит ни одна прямая 3 Вычесть его из всех элементов, через которые не проходят прямые 4 Прибавить его ко всем элементам, лежащим на пересечении прямых 5 Элементы, через которые проходит только одна прямая, оставить неизменными
uses crt; const n=4; ar:array[1..n,1..n] of byte=((0,1,1,0), (2,1,0,1), (3,1,0,1), (4,0,0,0)); Type TElement=record info:byte; checked:boolean; end; TRes=record ind,n:byte; end; Var mas:array[1..n,1..n] of TElement;
procedure init; var i,j:byte; begin for i:=1 to n do for j:=1 to n do begin mas[i,j].info:=ar[i,j]; mas[i,j].checked:=false; end; end;
function GetMaxColumn:TRes;//находим столбик с максимальным количеством нулей var i,j,max:byte; res:TRes; begin max:=0; res.n:=0; res.ind:=0; for i:=1 to n do begin for j:=1 to n do if (mas[j,i].info=0) and (mas[j,i].checked=false) then inc(max); if max>res.n then begin res.n:=max; res.ind:=i; end; max:=0; end; GetMaxColumn:=res; end;
function GetMaxLine:TRes;//находим строку с максимальным количеством нулей var i,j,max:byte; res:TRes; begin max:=0; res.n:=0; res.ind:=0; for i:=1 to n do begin for j:=1 to n do if (mas[i,j].info=0) and (mas[i,j].checked=false) then inc(max); if max>res.n then begin res.n:=max; res.ind:=i; end; max:=0; end; GetMaxLine:=res; end;
procedure CrossColumn(num:byte);//зачеркиваем столбик var i:byte; begin for i:=1 to n do mas[i,num].checked:=true; end;
procedure CrossLine(num:byte);//зачеркиваем строку var i:byte; begin for i:=1 to n do mas[num,i].checked:=true; end;
var NColumn,NLine:TRes; begin clrscr; init; repeat//повторяем NColumn:=GetMaxColumn; NLine:=GetMaxLine; if (NColumn.n<>0) and (NLine.n<>0) then if NColumn.n>NLine.n then //если количество нулей больше в столбце begin writeln('Column ',NColumn.ind); CrossColumn(NColumn.ind);//то зачеркиваем его end else// в противоположном случае begin writeln('Line ',NLine.ind); CrossLine(NLine.ind);// зачеркиваем линию end; until (NColumn.n=0) and (NLine.n=0);//пока не зачеркнем все нули readln; end.
Цитата
причем в поле info храним собственно значение (цифру), а в checked - информацию о зачеркнутости (0 - не зачеркнуто, 1 - зачеркнуто, 2 - находится на пересечении).
Хватит только 1 и 0, по-этому использую boolean.
Цитата
1) создаем дополнительный массив, в который записываем номера вычеркнутых строк и столбцов.
Этого не достаточно, надо хранить информацию о каждом элементе.
--------------------
Лао-Цзы : Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.