Проще всего сделать перебором, вот так, например:

uses crt;
const
 n=5;
 ar:array[1..n,1..n] of byte=
((1,0,0,0,1),
(1,1,1,1,0),
(0,1,1,1,0),
(0,1,1,1,1),
(1,0,0,0,1));
type TElement=record
      info:byte;
        checked:boolean;
    end;
mas_= array [1..n,1..n] of TElement;
Var y,mas:mas_;
mn,mnn,x,i,j:word;
b:boolean;
k:integer;
s1,s2,s11,s22:string;
 function IntToStr(I: Longint): String;
var
  S: string;
begin Str(I, S);  IntToStr := S;  end;
begin
mn:=n; mnn:=255; clrscr;
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;
for x:=0 to $ffff do begin
i:=0; y:=mas;
s1:=''; s2:='';
while (i+1)<=n do begin
if (1 shl i) and (x and $Ff)>0 then begin
for j:=1 to n do y[j,i+1].checked:=true;
s1:=s1+inttostr(i+1)+' '; end;
if ((1 shl i) and ((x and $Ff00) shr 8))>0 then begin
s2:=s2+inttostr(i+1)+' ';
for j:=1 to n do y[i+1,j].checked:=true; end;
inc (i);
end;
b:=true;
for i:=1 to n do for j:=1 to n do
if (y[i,j].info=0) and (y[i,j].checked=false) then b:=false;

j:=x; i:=0;
while j>0 do begin inc (i,j and 1); j:=j div 2; end;
if b and (i<=mn) then begin mn:=i; mnn:=x; s11:=s1; s22:=s2; end;
end;
writeln ('Всего-',mn);
writeln ('Столбцы-', s11);
writeln ('Строки- ',s22);
end.

Malice, можешь сделать небольшое пояснение алгоритма?

P.S. может кому надо - отформатированное чудо Malice-а (извиняюсь перед Malice-ом, просто так легче разобраться , имхо)
Нажмите для просмотра прикрепленного файла

Конечно Простой перебор, поясню немного:
1. x = 0..$FFFF - Вырианты зачеркиваний, в битовом представлении первые 8 бит - столбцы, вторые строки, 1-зачеркнут, 0 -нет
2. Зачеркиваем в соответствии с x
3. Проверяем все ли 0-ли зачеркнуты (там, где b)
4. считаем колво 1-ц в x
5. Сравниваем на минимум
Из типа x вытекает ограничение на размер матрицы (8 х 8), но перебор можно и иначе сделать, если что.
ps а что, хорошее форматирование, мне так, например, легче