wissqu.pas

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

{
ID:maigoak1
PROG:wissqu
}

program wissqu;
const
  dx:array[1..9]of shortint=(-1,-1,-1,0,0,0,1,1,1);
  dy:array[1..9]of shortint=(-1,0,1,-1,0,1,-1,0,1);
var
  fin,fout:text;
  map,old:array[0..5,0..5]of char;
  herd:array[1..16]of char;
  x,y:array[1..16]of byte;
  remain:array['A'..'E']of byte;
  v:array[1..4,1..4]of boolean;
  i,j:byte;
  total:longint;
procedure out;
  var
    i:byte;
  begin
    for i:=1 to 16 do
      writeln(fout,herd[i],' ',x[i],' ',y[i]);
  end;
procedure search(l:byte);
  var
    h,s,t:char;
    i,j:byte;
  function ok:boolean;
    var
      p:byte;
    begin
      ok:=false;
      for p:=1 to 9 do
        if map[i+dx[p],j+dy[p]]=h then exit;
      ok:=true;
    end;
  begin
    if l=1 then begin s:='D';t:='D';end
           else begin s:='A';t:='E';end;
    for h:=s to t do begin
      if remain[h]=0 then continue;
      dec(remain[h]);
      for i:=1 to 4 do
        for j:=1 to 4 do begin
          if v[i,j] then continue;
          if not ok then continue;
          herd[l]:=h;x[l]:=i;y[l]:=j;
          if l=16 then begin
            inc(total);
            if total=1 then out;
          end
          else begin
            map[i,j]:=h;
            v[i,j]:=true;
            search(l+1);
            map[i,j]:=old[i,j];
            v[i,j]:=false;
          end;
        end;
      inc(remain[h]);
    end;
  end;
begin
  assign(fin,'wissqu.in');
  reset(fin);
  fillchar(old,sizeof(old),' ');
  for i:=1 to 4 do begin
    for j:=1 to 4 do
      read(fin,old[i,j]);
    readln(fin);
  end;
  close(fin);
  map:=old;

  assign(fout,'wissqu.out');
  rewrite(fout);
  remain['A']:=3;remain['B']:=3;remain['C']:=3;remain['D']:=4;remain['E']:=3;
  total:=0;
  fillchar(v,sizeof(v),0);
  search(1);

  writeln(fout,total);
  close(fout);
end.