[Мы решаем ваши проблемы с Си и Паскалем ]
Главная » Статьи » Задачи с acm.timus.ru » Пакет решений на 15.03.08
1298
{ $A+,B-,D-,E+,F-,G-,I+,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X+}
{$M 65520,0,655360}

const maxn=20; maxm=maxn; maxmn=maxm*maxn;
 dx:array[1..8]of integer=(-2,-1,1,2, 2, 1,-1,-2);
 dy:array[1..8]of integer=( 1, 2,2,1,-1,-2,-2,-1);
 letters: array[1..11]of char=('a','b','c','d','e','f','g','h','i','j','k');

var b: array[-1..maxn+2,-1..maxm+2]of integer;
 path:array[1..maxmn,1..2]of integer;
var n: integer; nm: integer;
procedure ReadData;
begin
 Readln(n);
 nm:=n*n;
end;

procedure Solve(x,y: integer; i: integer; var yes: boolean);
var
xn,yn,xnn,ynn: integer;
j,k,m: integer; min: integer;
w:array[1..8]of integer;
begin
 for j:=1 to 8 do begin
  xn:=x+dx[j]; yn:=y+dy[j];
  if B[xn,yn]=0 then begin
   W[j]:=0;
   for k:=1 to 8 do begin
    xnn:=xn+dx[k]; ynn:=yn+dy[k];
    if B[xnn,ynn]=0 then inc(w[j]);
   end;
  end else W[j]:=maxint;
 end;

 j:=0;
 repeat Inc(j);

  m:=1; min:=w[1];
  for k:=2 to 8 do if W[k]<min then begin
   m:=k; min:=w[k];
  end;

  if min<>maxint then begin
   xn:=x+dx[m]; yn:=y+dy[m];
   B[xn,yn]:=i; path[i,1]:=yn; path[i,2]:=xn;

   if i<>NM then begin
    Solve(xn,yn,i+1,Yes);
    W[m]:=Maxint;
   end else Yes:=true;
   if not yes then B[xn,yn]:=0;
  end;
 until (j=8)or Yes;
end;

procedure print;
var i,j: integer;
begin
 for i:=1 to nm do writeln(letters[path[i,1]],path[i,2]);
end;

var i,j: integer;
 yes: boolean;
begin
 readdata;

 for i:=-1 to n+2 do
  for j:=-1 to n+2 do B[i,j]:=-1;
 for i:=1 to n do
  for j:=1 to n do B[i,j]:=0;

 if n=1 then begin writeln('a1');exit; end;

 Yes:=false;
 i:=1;
 while (i<=n div 2)and not yes do begin
  j:=1;
  while (j<=n div 2)and not yes do begin
   B[i,j]:=1; path[1,1]:=i; path[1,2]:=j;
   Solve(i,j,2,yes);
   if not yes then b[i,j]:=0;
   inc(j);
  end;
  inc(i);
 end;

 if not yes then writeln('IMPOSSIBLE') else print;
end.
Категория: Пакет решений на 15.03.08 | Добавил: solver (15.03.2008)
Просмотров: 1672