starry.pas

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

{
ID:maigoak1
PROG:starry
}

program starry;
const
  maxw=100;
  maxh=100;
  dx:array[1..8]of integer=(-1,-1,0,1,1,1,0,-1);
  dy:array[1..8]of integer=(0,1,1,1,0,-1,-1,-1);
type
  cluster=array[1..maxh,1..maxw]of boolean;
var
  fin,fout:text;
  map:array[0..maxh+1,0..maxw+1]of char;
  clu:array[1..27]of cluster;
  hi,wi:array[1..27]of byte;
  h,w,clus,i,j,t,b,l,r:byte;
procedure turn(n:byte);{Turn Cluster n by 90 degrees clockwise}
  var
    i,j,t:byte;
    c:cluster;
  begin
    for i:=1 to hi[n] do
      for j:=1 to wi[n] do
        c[j,hi[n]-i+1]:=clu[n][i,j];
    t:=hi[n];hi[n]:=wi[n];wi[n]:=t;
    clu[n]:=c;
  end;
procedure flip(n:byte);{Flip Cluster n horizontally}
  var
    i,j:byte;
    t:boolean;
  begin
    for i:=1 to hi[n] do
      for j:=1 to wi[n] div 2 do begin
        t:=clu[n][i,j];
        clu[n][i,j]:=clu[n][i,wi[n]-j+1];
        clu[n][i,wi[n]-j+1]:=t;
      end;
  end;
function equal(m,n:byte):boolean;
  var
    i,j:byte;
  begin
    equal:=false;
    if hi[m]<>hi[n] then exit;
    if wi[m]<>wi[n] then exit;
    for i:=1 to hi[n] do
      for j:=1 to wi[n] do
        if clu[m][i,j]<>clu[n][i,j] then exit;
    equal:=true;
  end;
function similar(n:byte):byte;
  {Return the number of the cluster similar to n, n if none}
  var
    i,j:byte;
  begin
    if n=1 then
      similar:=1
    else begin
      for i:=1 to 8 do begin
        for j:=1 to n-1 do
          if equal(n,j) then begin
            similar:=j;
            dec(clus);
            exit;
          end;
        case i of
          1,2,3,5,6,7:turn(n);
          4:          flip(n);
        end;
      end;
      similar:=n;
    end;
  end;
procedure floodfill(x,y:byte;c1,c2:char);
  var
    d:byte;
  begin
    if map[x,y]<>c1 then exit;
    map[x,y]:=c2;
    if x<t then t:=x else if x>b then b:=x;
    if y<l then l:=y else if y>r then r:=y;
    for d:=1 to 8 do
      floodfill(x+dx[d],y+dy[d],c1,c2);
  end;
procedure storeclu;
  var
    i,j:byte;
  begin
    inc(clus);
    hi[clus]:=b-t+1;wi[clus]:=r-l+1;
    for i:=1 to hi[clus] do
      for j:=1 to wi[clus] do
        clu[clus][i,j]:=map[t-1+i,l-1+j]='2';
  end;
begin
  assign(fin,'starry.in');
  reset(fin);
  readln(fin,w);
  readln(fin,h);
  for i:=1 to h do begin
    for j:=1 to w do
      read(fin,map[i,j]);
    readln(fin);
  end;
  close(fin);

  for i:=0 to w+1 do begin
    map[0,i]:='0';
    map[h+1,i]:='0';
  end;
  for i:=1 to h do begin
    map[i,0]:='0';
    map[i,w+1]:='0';
  end;

  clus:=0;
  for i:=1 to h do
    for j:=1 to w do
      if map[i,j]='1' then begin
        t:=i;b:=i;l:=j;r:=j;
        floodfill(i,j,'1','2');
        storeclu;
        floodfill(i,j,'2',chr(96+similar(clus)));
      end;

  assign(fout,'starry.out');
  rewrite(fout);
  for i:=1 to h do begin
    for j:=1 to w do
      write(fout,map[i,j]);
    writeln(fout);
  end;
  close(fout);
end.