cover.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 112 行

{
PROB:cover
LANG:PASCAL
}

{Min covering = max matching -- I didn't know this theorem in contest!!!
 If we know this, this prob is almost the same as, or rather,
   easier than tju1088.}
program cover;
const
  maxsize=50;
  maxstrips=sqr(maxsize) shr 1;
type
  strip=record p,s,e:byte;end;
  striplist=array[0..maxstrips+1]of strip;
var
  map:array[1..maxsize,1..maxsize]of char;
  x,y:striplist;
  from,till:array[1..maxsize]of word;
  my:array[1..maxstrips]of word;
  vy:array[1..maxstrips]of boolean;
  m,n,i,j,cx,cy:word;
function max(a,b:word):word;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure getstrips(var a:striplist;var c,m,n:word);
  var
    open:boolean;
  begin
    c:=0;
    for i:=1 to m do begin
      open:=false;
      for j:=1 to n do
        case map[i,j] of
          '*':if not open then begin open:=true;inc(c);a[c].p:=i;a[c].s:=j;end;
          '.':if open then begin open:=false;a[c].e:=j-1;end;
        end;
      if open then a[c].e:=n;
    end;
  end;
procedure flip;
  var
    c:char;
  begin
    for i:=2 to max(m,n) do
      for j:=1 to i-1 do begin
        c:=map[i,j];map[i,j]:=map[j,i];map[j,i]:=c;
      end;
  end;
procedure calfromtill;
  begin
    y[0].p:=0;y[cy+1].p:=n+1;
    j:=1;
    for i:=1 to n do begin
      from[i]:=j;
      while y[j].p=i do inc(j);
    end;
    j:=cy;
    for i:=n downto 1 do begin
      till[i]:=j;
      while y[j].p=i do dec(j);
    end;
  end;
function cross(a,b:word):boolean;
  begin
    cross:=(x[a].p>=y[b].s) and (x[a].p<=y[b].e) and
           (y[b].p>=x[a].s) and (y[b].p<=x[a].e);
  end;
function find(v:word):boolean;
  var
    i:word;
  begin
    for i:=from[x[v].s] to till[x[v].e] do
      if (my[i]=0) and cross(v,i) then begin
        find:=true;my[i]:=v;exit;
      end;
    for i:=from[x[v].s] to till[x[v].e] do
      if not vy[i] and cross(v,i) then begin
        vy[i]:=true;
        if find(my[i]) then begin
          find:=true;my[i]:=v;exit;
        end;
      end;
    find:=false;
  end;
begin
  assign(input,'cover.in');reset(input);
  assign(output,'cover.out');rewrite(output);

  read(m,n);
  for i:=1 to m do begin
    readln;
    for j:=1 to n do
      read(map[i,j]);
  end;

  getstrips(x,cx,m,n);
  flip;
  getstrips(y,cy,n,m);
  calfromtill;

  fillchar(my,sizeof(my),0);n:=0;
  for i:=1 to cx do begin
    fillchar(vy,sizeof(vy),0);
    if find(i) then inc(n);
  end;
  writeln(n);

  close(input);close(output);
end.