betsy.pas

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

{
ID:maigoak1
PROG:betsy
}

program betsy;
const
  maxn=7;
  dx:array[1..4]of shortint=(-1,1,0,0);
  dy:array[1..4]of shortint=(0,0,-1,1);
var
  fin,fout:text;
  v:array[0..maxn+1,0..maxn+1]of boolean;
  adj:array[0..maxn+1,0..maxn+1]of byte;
  n,maxlv,i,j:byte;
  count:longint;
procedure search(x,y,lv,dir:byte);
  var
    d,l,r,bx,by,lx,ly,rx,ry,fx,fy,flx,fly,frx,fry:byte;
  begin
    if v[x,y] then exit;
    if (x=n) and (y=1) then exit;
    if lv=maxlv then begin inc(count);exit;end;

    if dir>2 then begin l:=1;r:=2;end else begin l:=3;r:=4;end;
    fx:=x+dx[dir];fy:=y+dy[dir];
    lx:=x+dx[l];ly:=y+dy[l];rx:=x+dx[r];ry:=y+dy[r];
    if v[fx,fy] and (not v[lx,ly]) and (not v[rx,ry]) then exit;
    flx:=fx+dx[l];fly:=fy+dy[l];
    if v[flx,fly] and (not v[fx,fy]) and (not v[lx,ly]) then exit;
    frx:=fx+dx[r];fry:=fy+dy[r];
    if v[frx,fry] and (not v[fx,fy]) and (not v[rx,ry]) then exit;

    v[x,y]:=true;
    bx:=x-dx[dir];by:=y-dy[dir];
    for d:=1 to 4 do
      if not ((bx+dx[d]=n) and (by+dy[d]=1)) and (not v[bx+dx[d],by+dy[d]]) then
        if adj[bx+dx[d],by+dy[d]]=2 then begin v[x,y]:=false;exit;end;
    for d:=1 to 4 do
      dec(adj[bx+dx[d],by+dy[d]]);

    for d:=1 to 4 do
      search(x+dx[d],y+dy[d],lv+1,d);

    v[x,y]:=false;
    for d:=1 to 4 do
      inc(adj[bx+dx[d],by+dy[d]]);
  end;
begin
  assign(fin,'betsy.in');
  reset(fin);
  readln(fin,n);
  close(fin);
  maxlv:=n*n-1;

  for i:=1 to n do begin
    v[0,i]:=true;v[n+1,i]:=true;
    v[i,0]:=true;v[i,n+1]:=true;
    adj[0,i]:=1;adj[n+1,i]:=1;
    adj[i,0]:=1;adj[i,n+1]:=1;
  end;
  for i:=1 to n do
    for j:=1 to n do begin
      v[i,j]:=false;
      adj[i,j]:=4-ord((i=1) or (i=n))-ord((j=1) or (j=n));
    end;

  if n=1 then
    count:=1
  else begin
    count:=0;
    v[1,1]:=true;
    search(1,2,2,4);
    search(2,1,2,2);
  end;

  assign(fout,'betsy.out');
  rewrite(fout);
  writeln(fout,count);
  close(fout);
end.