Matritsa Опции

[-programmer-]

дана матрица из 0 и 1 в
данной матрицы найти максимальную подматрицу состоящую из 0
Так вот проблема в чем
каждый элемент матрицы посещается не более 1 раза

[virt]

program max_podmatr;
const max_n = 20;
var a : array[1..max_n,0..max_n]of byte;
    b : array[1..max_n,1..max_n]of byte;
    i,j,n,m,k : integer;
    max : longint;
    width : byte;

function min(a,b : integer) : integer;
begin
   if  a < b then min := a else min := b;
end;

begin
   read(n,m);
   for i := 1 to n do
      for j := 1 to m do
         read(b[i,j]);
   fillchar(a,sizeof(a),0);
   max := 0;
   for i := 1 to n do
      for j := 1 to m do
         if b[i,j] = 0 then a[i,j] := a[i,j - 1] + 1 else a[i,j] := 0;
   for i := 1 to n do
      for j := 1 to m do
         begin
            width := a[i,j];
            for k := i downto 1 do
               begin
                  width := min (width,a[k,j]);
                  if width * (i - k + 1) > max then max := width * (i - k + 1);
               end;
         end;
   writeln(max);
end.

сложность O(n^3)