golygon.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

program golygons;
type
  tp=array[-110..110,-110..110] of byte;
  tr=array[0..22,-210..210] of byte;
  dir=array[1..4,1..2] of shortint;
  dirtory=array[0..20] of byte;
  step_tp=array[0..20,1..2] of integer;
const in_file='golygon.dat';out_file='golygon.out';
      d:dir=((0,1),(0,-1),(1,0),(-1,0));
      er:array[1..4] of char=('n','s','e','w');
var city:tp;	{定义城市}
    walk:dirtory;
    step:step_tp;	{每一步的坐标}
    refer:tr;
    in_f,out_f:text;
    n,h:integer;
    bb:boolean;
    tot:longint;
procedure input;
var i,x,y:integer;
begin
  fillchar(city,sizeof(city),0);
  assign(in_f,in_file);
  reset(in_f);
  readln(in_f,n);
  readln(in_f,h);
  for i:=1 to h do
  begin
    readln(in_f,x,y);
    city[x,y]:=1;
  end;
  close(in_f);
end;

procedure mark(x,y:shortint;sp,dir:byte);	{将走过的点作标记}
var i,x1,y1:shortint;
begin
  x1:=step[sp-1,1];y1:=step[sp-1,2];
  for i:=1 to sp do
  begin
    x1:=x1+d[dir,1];
    y1:=y1+d[dir,2];
    city[x1,y1]:=1;
  end;
end;

procedure clear(x,y:shortint;sp,dir:byte);	{将走过的点清标记}
var i,x1,y1:shortint;
begin
  x1:=step[sp-1,1];y1:=step[sp-1,2];
  for i:=1 to sp do
  begin
    x1:=x1+d[dir,1];
    y1:=y1+d[dir,2];
    if (x1<>0) or (y1<>0) then
      city[x1,y1]:=0;
  end;
end;

procedure t(sp:byte);	{搜索过程}
var i,j,x,y:shortint;
begin
  if (step[sp-1,1]=step[sp-1,2]) and (step[sp-1,1]=0) then
  begin
    if sp<=n then exit;
    for i:=1 to sp-1 do
      write(out_f,er[walk[i]]);
    writeln(out_f);
    inc(tot);
    exit;
  end;
  if sp>n then exit;
  for i:=1 to 4 do
    if i<>walk[sp-1] then
    begin
      bb:=false;
      x:=step[sp-1,1];
      y:=step[sp-1,2];
      walk[sp]:=i;
      for j:=1 to sp do
      begin
        x:=x+d[i,1];
        y:=y+d[i,2];
        if (city[x,y]<>0) and ((j<>sp) or (x<>0) or (y<>0)) then
        begin
          bb:=true;
          break;
        end;
      end;

      if not bb then
      begin
        step[sp,1]:=x;
        step[sp,2]:=y;
        if ((i<3) and (refer[sp+2,y]=1)) or ((i>2) and (refer[sp+2,x]=1)) or (sp+2>=n) then
        begin
          mark(x,y,sp,i);
          t(sp+1);
          clear(x,y,sp,i)
        end;
      end;
    end;
end;

procedure make(n:byte);	{第五步的预处理}
var i,j,k,p:integer;
begin
  fillchar(refer,sizeof(refer),0);
  for i:=1 to n do
  begin
    refer[i,i]:=1;
    refer[i,-i]:=1;
    j:=i+2;
    while (j<=n) do
    begin
      p:=((j-2)*(j-1)) div 2;
      for k:=-p to p do
        if refer[i,k]=1 then
        begin
          refer[i,k+j]:=1;
          refer[i,k-j]:=1;
          refer[i,j-k]:=1;
        end;

      j:=j+2;
    end;
  end;
end;

procedure main;
var i,j,x,y:integer;
begin
  make(n);
  assign(out_f,out_file);
  rewrite(out_f);
  tot:=0;
  step[0,1]:=0;
  step[0,2]:=0;
  city[0,0]:=1;
  if refer[1,0]=1 then
    for i:=1 to 4 do
    begin
      x:=d[i,1];y:=d[i,2];
      walk[1]:=i;
      step[1,1]:=x;
      step[1,2]:=y;
      if ((i<3) and (refer[3,y]=1)) or ((i>2) and (refer[3,x]=1)) then
      begin
        mark(x,y,1,i);
        t(2);
        clear(x,y,1,i);
      end;
    end;

  writeln(out_f,'Found ',tot,' golygon(s).');
  close(out_f);
end;

begin
  input;
  main;
end.