回 帖 发 新 帖 刷新版面

主题:求助:圆桌骑士问题

很多世纪以前,阿瑟王和他的圆桌武士常在每年元旦聚会庆祝他们的友谊。我们用一个单人玩的棋盘游戏去纪念这个史实:一个国王和多个武士被随机放在8X8的正方形棋盘的不同方格上。只要不越出棋盘,国王可以移至与之相邻的方格内,只要不越出棋盘,武士可以跳日字,在棋局当中,选手可以在同一方格内摆放多个棋子,选手的目标是在尽可能少的步数内把所有的棋子集中到同一方格。为此,他必须按前述方法去移动棋子。此外,当国王和一个或多个武士位于同一方格内时,选手可以选择此后让国王跟随其中一个武士一同向聚会终点移动,就象移动单个武士一样。任务:写出一个程序去计算选手要实现聚会所需最少的移动次数。
输入数据:文件camelot.in包括了以字符串表示的棋盘初始状态。该字符串包含了一串最多有64个不同的棋子位置:首先是国王的位置,而随后是武士们的位置。每个位置由一对字母-数字表示:字母表示棋盘水平坐标,而数字表示棋盘垂直坐标。
输入实例:
D4A3A8H1H8
输出数据:
文件camelot.out必须包含单一的一行,以一个正整数表示选手要实现聚会所需最少的移动次数。
输出实例:
10

回复列表 (共1个回复)

沙发

const 
 go:array[1..8,1..2]of -2..2=((1,-2),(-2,1),(-1,2),(2,-1),(-1,-2),(-2,-1),(1,2),(2,1)); 
type 
 ts=record 
 x,y:byte; 
 end; 
var 
 pair:array[1..8,1..8]of byte; 
 dis:array[1..8,1..8,1..8,1..8]of byte; 
 all:array[1..8,1..8]of integer; 
 s:array[1..64]of ts; 
 king:ts; 
 k_num,i:integer; 
 best:integer; 
procedure init; 
var 
 ss:string; 
 ch:char; 
 no:byte; 
begin 
 assign(input,'input.txt'); 
 reset(input); 
 { read(ch); 
 king.y:=ord(ch)-64; 
 read(ch); 

 king.x:=ord(ch)-48; 
 k_num:=0; 
 while not eof do begin 
 inc(k_num); 
 read(ch); 
 s[k_num].y:=ord(ch)-64; 
 read(ch); 
 s[k_num].x:=ord(ch)-48; 
 end; } 
 readln(ss); 
 king.x:=ord(ss[1])-64; 
 king.y:=ord(ss[2])-48; 

 //for i:=3 to length(ss) do 
 i:=2; 
 while i<length(ss) do 
 begin 
 inc(k_num); 
 inc(i); 
 s[k_num].x:=ord(ss[i])-64; 
 inc(i); 
 s[k_num].y:=ord(ss[i])-48; 
 end; 
close(input); 
end; 
// 
procedure bfs(s1,s2:byte); 
 var 
 stack:array[1..70,1..2]of byte; 
 s,t,i:byte; 
 x,y:integer; 
 begin 
 fillchar(stack,sizeof(stack),0); 
 s:=0; 
 t:=1; 
 stack[1,1]:=s1; 
 stack[1,2]:=s2; 
 repeat 
 inc(s); 
 for i:=1 to 8 do 
 begin 
 x:=stack[s,1]+go[i,1]; 
 y:=stack[s,2]+go[i,2]; 
 if (x>=1)and(x<=8)and(y>=1)and(y<=8) and(not((x=s1)and(y=s2)))and(dis[s1,s2,x,y]=0) 
 then begin 
 dis[s1,s2,x,y]:=dis[s1,s2,stack[s,1],stack[s,2]]+1; 
 inc(t); 
 stack[t,1]:=x; 
 stack[t,2]:=y; 
 end; 
 end; 
 until s=t; 
end; 

 // end; 
procedure get_dis; 
 var 
 i,j,k:byte; 
 begin 
 for i:=1 to 8 do 
 for j:=1 to 8 do 
 begin 
 bfs(i,j); 
 for k:=1 to k_num do inc(all[i,j],dis[i,j,s[k].x,s[k].y]); 
 end; 
 end; 
{procedure get_dis; 
 var 
 i,j,ii,jj,k1,k2,min:integer; 

 begin 

 for i:=1 to 8 do 
 for j:=1 to 8 do 
 begin 
 for ii:=1 to 8 do 
 for jj:=1 to 8 do 
 begin 
 for k1:=1 to 8 do 
 for k2:=1 to 8 do 
 begin 
 min:= 


 end; 


 end;} 
// 
procedure get_ans; 
 var 
 i,j,k:byte; 
 ii,jj:byte; 
 min,now:integer; 
 begin 

 best:=maxint; 
 for i:=1to 8 do 
 for j:=1 to 8 do 
 begin 
 min:=all[i,j]+abs(king.x-i)+abs(king.y-j); 
 for ii:=1 to 8 do 
 for jj:=1 to 8 do 
 begin 
 for k:=1 to k_num do 
 begin 
 now:=all[i,j]-dis[s[k].x,s[k].y,i,j]+dis[s[k].x,s[k].y,ii,jj] 
 +abs(king.x-ii)+abs(king.y-jj)+dis[ii,jj,i,j]; 
 if now<min then min:=now; 
 end; 
 end; 
 if min<best then best:=min; 
 end; 
 end; 

procedure outs; 
 begin 
 assign(output,'output.txt'); 
 rewrite(output); 
 writeln(best); 
 close(output); 
 end; 

begin 
 init; 
 get_dis; 
 get_ans; 
 outs; 
 {i:=3; 
 while i<8 do 
 begin 
 inc(i); 
 writeln(i); 
 end;} 
 {i:=3; 
 repeat 
 inc(i); 
 writeln(i); 
 until i>8; } 

end.

我来回复

您尚未登录,请登录后再回复。点此登录或注册