切换到宽版
发帖 回复
返回列表
  • 7489阅读
  • 5回复

Checker Challenge 跳棋的挑战 [复制链接]

 上一主题 下一主题
离线danielzcc
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2006-02-06
文字
USACO （Section 1.4 ）中的 Checker Challenge 跳棋的挑战 怎么做时间才能最短。
大家帮帮忙呀。
只要能通过就行。
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线archimedes
管理员
只看该作者 1 发表于: 2006-02-07
剪枝，剪枝，剪枝，再剪枝
程序到网上去抄标程
回复
举报
离线danielzcc
OIFans入门选手
只看该作者 2 发表于: 2006-02-08
哪里有好的标程，请告知一二，谢谢
回复
举报
离线stevenjl
管理员
只看该作者 3 发表于: 2006-02-08
楼主可是温州中学的？你参加今年的NOIP复赛了吗？……绍兴的那个……
Dream Walker...
回复
举报
离线stevenjl
管理员
只看该作者 4 发表于: 2006-02-08
复制代码
  1. Program Checker;
  2.   Var diagPLUS: Array[2..30] Of Boolean;
  3.     diagMINUS: Array[-15..15] Of Boolean;
  4.     sol: Array[1..15] Of ShortInt;
  5.     i,n,found: Longint;
  6.     stop: Boolean;
  7.     next,prev: Array[0..16] Of ShortInt;
  8.     sy: ShortInt;
  10. Procedure Search0(y:ShortInt);
  11.   Var x,i:ShortInt;
  12. Begin
  13.   If stop Then Exit;
  14.   If y=n+1 Then Begin
  15.     Inc(found);
  16.     If found<4 Then Begin
  17.         For i:=1 To n-1 Do
  18.           Write(sol[i],' ');
  19.         Writeln(sol[n]);
  20.     End Else
  21.     stop:=True;
  22.     Exit;
  23.   End;
  24.   If sol[y]<>0 Then Begin
  25.     Search0(y+1);
  26.     Exit;
  27.   End;
  28.   x:=next[0];
  29.   While x<=n Do Begin
  30.     If Not ((diagPLUS[x+y]) Or (diagMINUS[x-y])) Then Begin
  31.         sol[y]:=x;
  32.         diagPLUS[x+y]:=True;
  33.         diagMINUS[x-y]:=True;
  34.         next[prev[x]]:=next[x];
  35.         prev[next[x]]:=prev[x];
  36.         Search0(y+1);
  37.         diagPLUS[x+y]:=False;
  38.         diagMINUS[x-y]:=False;
  39.         next[prev[x]]:=x; prev[next[x]]:=x;
  40.     End;
  41.     x:=next[x];
  42.   End;
  43.   sol[y]:=0;
  44. End;
  46. Procedure Search;
  47.   Var x:ShortInt;
  48. Begin
  49.   If sy=n+1 Then Begin
  50.     Inc(found);
  51.     Exit;
  52.   End;
  53.   If sol[sy]<>0 Then Begin
  54.     Inc(sy);
  55.     Search;
  56.     Dec(sy);
  57.     Exit;
  58.   End;
  59.   x:=next[0];
  60.   While x<=n Do Begin
  61.     If Not ((diagPLUS[x+sy]) Or (diagMINUS[x-sy])) Then Begin
  62.         sol[sy]:=x;
  63.         diagPLUS[x+sy]:=True;
  64.         diagMINUS[x-sy]:=True;
  65.         next[prev[x]]:=next[x];
  66.         prev[next[x]]:=prev[x];
  67.         Inc(sy);
  68.         Search;
  69.         Dec(sy);
  70.         diagPLUS[x+sy]:=False;
  71.         diagMINUS[x-sy]:=False;
  72.         next[prev[x]]:=x;
  73.         prev[next[x]]:=x;
  74.     End;
  75.     x:=next[x];
  76.   End;
  77.   sol[sy]:=0;
  78. End;
  80. Procedure Search2(miny:Longint);
  81.   Var x,y,i:ShortInt;
  82.       curf:Longint;
  83. Begin
  84.   x:=n Div 2+1;
  85.   For y:=miny To n Div 2 Do
  86.     If Not (diagPLUS[x+y] Or diagMINUS[x-y]) Then Begin
  87.         curf:=found;
  88.         sol[y]:=x;
  89.         diagPLUS[x+y]:=True;
  90.         diagMINUS[x-y]:=True;
  91.         next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
  92.         sy:=1;
  93.         Search;
  94.         If y>miny Then
  95.           found:=found+(found-curf);
  96.         sol[y]:=0;
  97.         diagPLUS[x+y]:=False;
  98.         diagMINUS[x-y]:=False;
  99.         next[prev[x]]:=x; prev[next[x]]:=x;
  100.     End;
  101. End;
  103. Procedure Search1;
  104.   Var x,y,i:ShortInt;
  105. Begin
  106.   y:=n Div 2+1;
  107.   For x:=1 To n Div 2 Do Begin
  108.     sol[y]:=x;
  109.     diagPLUS[x+y]:=True;
  110.     diagMINUS[x-y]:=True;
  111.     next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
  112.     Search2(x);
  113.     diagPLUS[x+y]:=False;
  114.     diagMINUS[x-y]:=False;
  115.     next[prev[x]]:=x; prev[next[x]]:=x;
  116.   End;
  117.   sol[y]:=0;
  118.   found:=found*4;
  119.   x:=n Div 2+1;
  120.   sol[y]:=x;
  121.   diagPLUS[x+y]:=True;
  122.   diagMINUS[x-y]:=True;
  123.   next[prev[x]]:=next[x]; prev[next[x]]:=prev[x];
  124.   sy:=1;
  125.   Search;
  126. End;
  128. Begin
  129.   Assign(Input,'checker.in'); Reset(Input);
  130.   Assign(Output,'checker.out'); Rewrite(Output);
  131.   Read(n);
  132.   found:=0;
  133.   FillChar(diagPLUS,SizeOf(diagPLUS),False);
  134.   FillChar(diagMINUS,SizeOf(diagMINUS),False);
  135.   FillChar(sol,SizeOf(sol),0);
  136.   For i:=0 To n+1 Do Begin
  137.     prev[i]:=i-1;
  138.     next[i]:=i+1;
  139.   End;
  140.   If n Mod 2=0 Then Begin
  141.     stop:=False;
  142.     Search0(1);
  143.     sy:=1;
  144.     found:=0;
  145.     Search;
  146.   End Else Begin
  147.     stop:=False;
  148.     Search0(1);
  149.     found:=0;
  150.     Search1;
  151.   End;
  152.     Writeln(found);
  153.     Close(Output);
  154. End.
Dream Walker...
回复
举报
离线lipeiqian
OIFans入门选手
只看该作者 5 发表于: 2006-06-11
复制代码
  1. /*
  2. TASK: checker
  3. LANG: C++
  4. */
  6. #include <fstream>
  8. using namespace std;
  10. ifstream fin("checker.in");
  11. ofstream fout("checker.out");
  13. int n,pr=0,p=0,h[15];
  14. char c[15],db[40],dc[28];
  16. void work(int k)
  17. {
  18.   int i;
  19.   if(k>n)
  20.   {
  21.     p+=2;
  22.     if(n%2==1&&h[1]==(n+1)/2||n<=6) p--;
  23.     if(++pr<=3)
  24.     {
  25.         for(i=1;i<n;i++) fout<<h[i]<<' ';
  26.         fout<<h[n]<<endl;
  27.     }
  28.     return;
  29.   }
  30.   for(i=1;i<=(k==1&&n>6?(n+1)/2:n);i++)
  31.   {
  32.     if(db[i+k]==0&&dc[k-i+15]==0&&c[i]==0)
  33.     {
  34.         h[k]=i;
  35.         db[i+k]=1;
  36.         dc[k-i+15]=1;
  37.         c[i]=1;
  38.         work(k+1);
  39.         db[i+k]=0;
  40.         dc[k-i+15]=0;
  41.         c[i]=0;
  42.     }
  43.   }
  44. }
  46. int main()
  47. {
  48.   fin>>n;
  49.   work(1);
  50.   fout<<p<<endl;
  51.   return 0;
  52. }
回复
举报
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个