frameup.pas

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

{
ID:maigoak1
PROG:frameup
}

program frameup;
const
  max=30;
var
  fin,fout:text;
  map:array[1..max,1..max]of char;
  left,right,top,bottom,indeg:array['A'..'Z']of byte;
  under:array['A'..'Z','A'..'Z']of boolean;
  s:array[1..26]of char;
  v:array['A'..'Z']of boolean;
  h,w,letters,i,j:byte;
  c:char;
procedure overlap(a,b:char);{Put a under b}
  begin
    if not under[a,b] then begin
      under[a,b]:=true;
      inc(indeg[b]);
    end;
  end;
procedure out;
  var
    i:byte;
  begin
    for i:=1 to letters do
      write(fout,s[i]);
    writeln(fout);
  end;
procedure toposort(l:byte);
  var
    c,d:char;
  begin
    for c:='A' to 'Z' do
      if (not v[c]) and (indeg[c]=0) then begin
        s[l]:=c;
        if l=letters then
          out
        else begin
          v[c]:=true;
          for d:='A' to 'Z' do
            if under[c,d] then
              dec(indeg[d]);
          toposort(l+1);
          v[c]:=false;
          for d:='A' to 'Z' do
            if under[c,d] then
              inc(indeg[d]);
        end;
      end;
  end;
begin
  fillchar(v,sizeof(v),1);
  assign(fin,'frameup.in');
  reset(fin);
  readln(fin,h,w);
  for i:=1 to h do begin
    for j:=1 to w do begin
      read(fin,map[i,j]);
      if map[i,j]<>'.' then
        if v[map[i,j]] then begin
          v[map[i,j]]:=false;
          inc(letters);
        end;
    end;
    readln(fin);
  end;
  close(fin);

  fillchar(left,sizeof(left),0);
  fillchar(right,sizeof(right),0);
  fillchar(top,sizeof(top),0);
  fillchar(bottom,sizeof(bottom),0);
  for i:=1 to w do
    for j:=1 to h do
      if map[j,i]<>'.' then if left[map[j,i]]=0 then left[map[j,i]]:=i;
  for i:=w downto 1 do
    for j:=1 to h do
      if map[j,i]<>'.' then if right[map[j,i]]=0 then right[map[j,i]]:=i;
  for i:=1 to h do
    for j:=1 to w do
      if map[i,j]<>'.' then if top[map[i,j]]=0 then top[map[i,j]]:=i;
  for i:=h downto 1 do
    for j:=1 to w do
      if map[i,j]<>'.' then if bottom[map[i,j]]=0 then bottom[map[i,j]]:=i;

  fillchar(under,sizeof(under),0);
  fillchar(indeg,sizeof(indeg),0);
  for c:='A' to 'Z' do
    if not v[c] then begin
      for i:=left[c] to right[c] do begin
        if map[top[c],i]<>c then overlap(c,map[top[c],i]);
        if map[bottom[c],i]<>c then overlap(c,map[bottom[c],i]);
      end;
      for i:=top[c]+1 to bottom[c]-1 do begin
        if map[i,left[c]]<>c then overlap(c,map[i,left[c]]);
        if map[i,right[c]]<>c then overlap(c,map[i,right[c]]);
      end;
    end;

  assign(fout,'frameup.out');
  rewrite(fout);
  toposort(1);
  close(fout);
end.