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)

[-programmer-]

сложность должна быть O(n^2)

[virt]

значит надо искать именно максимальную квадратную матрицу.

[virt]

program max_square_podmatr;
const max_n = 20;
var a : array[0..max_n,0..max_n]of byte;
    i,j,n,m : integer;
    sc : integer;
    max : integer;

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

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

сложность O(n^2)
находит максимальный квадрат.