伊莉討論區

標題: 騎士周游問題的代碼 [打印本頁]
作者: zhazhaniu2    時間: 2009-8-26 10:58 AM     標題: 騎士周游問題的代碼

騎士周游問題：給出m×n的棋盤，還有給出馬的起始位置，求出一條路線，使馬能跳完棋盤上所有格子以后回到起點

我們上學期的一個作業，優化了很久呢～算3000×3000的棋盤分配好內存后只需要二十秒左右可以求得一個解，不過要爆棧，不爆棧的話因為是遞歸的，所以只能算到78×78的棋盤（不知道什么是爆棧和怎么爆棧的話google一下吧～呵呵呵～）

代碼貼上來，給需要的人做個參考吧～

  2. #include <iostream>
  3. #include <fstream>
  4. #include<iomanip>
  5. #include <algorithm>
  6. using namespace std;
  7. bool finish(int i,int j);
  8. int startx,starty,m,n,grid[3010][3010],endstep,nowi,nowj;
  9. struct Point
  10. {
  11. int x,y;
  12. }pos[9];
  13. struct P
  14. {
  15. int No,mark;
  16. };
  17. bool less_2(const P & p1, const P & p2)
  18. {
  19. if(p1.mark<p2.mark || p1.No==-1 || p2.No==-1)
  20.   return p1.mark<p2.mark;
  21. else if(p1.mark==p2.mark)return (pos[p1.No].x+nowi-m/2)*(pos[p1.No].x+nowi-m/2)+(pos[p1.No].y+nowj-n/2)*(pos[p1.No].y+nowj-n/2)>(pos[p2.No].x+nowi-m/2)*(pos[p2.No].x+nowi-m/2)+(pos[p2.No].y+nowj-n/2)*(pos[p2.No].y+nowj-n/2);
  22. else return 0;
  23. }
  24. void output2()
  25. {
  26. int i,j;
  27. ofstream a("c:\\a.txt");
  28. for(i=1;i<=m;++i)
  29. {
  30.   for(j=1;j<=n;++j)
  31.   {
  32.    a<<grid[i][j]<<' ';
  33.   }
  34.   a<<endl;
  35. }
  36. a.close();
  37. }
  38. void output()
  39. {
  40. int i,j;
  41. for(i=1;i<=m;++i)
  42. {
  43.   for(j=1;j<=n;++j)
  44.   {
  45.    cout<<setw(3)<<grid[i][j]<<' ';
  46.   }
  47.   cout<<endl;
  48. }
  49. }
  50. void init()
  51. {
  52. pos[8].x=1,pos[8].y=-2;
  53. pos[1].x=2,pos[1].y=-1;
  54. pos[2].x=2,pos[2].y=1;
  55. pos[7].x=1,pos[7].y=2;
  56. pos[3].x=-1,pos[3].y=2;
  57. pos[6].x=-2,pos[6].y=1;
  58. pos[5].x=-2,pos[5].y=-1;
  59. pos[4].x=-1,pos[4].y=-2;
  60. cout<<"請輸入棋盤大小(m n):";
  61. cin>>m>>n;
  62. cout<<"請輸入馬的起始坐標(x y):";
  63. cin>>startx>>starty;
  64. endstep=m*n;
  65. memset(grid,0,sizeof(grid));
  66. }
  67. int predict(int i,int j)
  68. {
  69. int k,prei,prej,result=0;
  70. for(k=1;k<=8;++k)
  71. {
  72.   prei=i+pos[k].x;
  73.   prej=j+pos[k].y;
  74.   if(prei>0 && prei<=m && prej>0 && prej<=n && grid[prei][prej]==0)++result;
  75. }
  76. return result;
  77. }
  78. void mark(int i,int j,P *p,int step)
  79. {
  80. int k,prei,prej;
  81. for(k=1;k<=8;++k)
  82. {
  83.   prei=i+pos[k].x;
  84.   prej=j+pos[k].y;
  85.   if(prei>0 && prei<=m && prej>0 && prej<=n && grid[prei][prej]==0){p[k-1].mark=predict(prei,prej);p[k-1].No=k;}
  86.   else {p[k-1].No=-1;p[k-1].mark=9999;}
  87. }
  88. sort(p,p+8,less_2);
  89. }
  90. bool finish(int i,int j)
  91. {
  92. int k,prei,prej;
  93. for(k=1;k<=8;++k)
  94. {
  95.   prei=i+pos[k].x;
  96.   prej=j+pos[k].y;
  97.   if(prei>0 && prei<=m && prej>0 && prej<=n && grid[prei][prej]==1)return 1;
  98. }
  99. return 0;
  100. }
  101. bool jump(int i,int j,int step)
  102. {
  103. int k;
  104. grid[i][j]=step;
  105. nowi=i,nowj=j;
  106. P p[8];
  107. mark(i,j,p,step);
  108. if(step==endstep)
  109. {
  110.   if(finish(i,j))return 1;
  111.   else grid[i][j]=0;return 0;
  112. }
  113. else
  114. {
  115.   for(k=0;p[k].mark<9999;++k)
  116.   {
  117.    if(jump(i+pos[p[k].No].x,j+pos[p[k].No].y,step+1))return 1;
  118.   }
  119.   grid[i][j]=0;
  120. }
  121. return 0;
  122. }
  123. void transf(int a,int b)
  124. {
  125. int i,j,base=grid[a][b];
  126. for(i=1;i<=m;++i)
  127.   for(j=1;j<=n;++j)
  128.    if(grid[i][j]>=base)grid[i][j]-=(base-1);
  129.    else grid[i][j]=grid[i][j]-base+n*n+1;
  130. }

  132. int main(int argc, char* argv[])
  133. {
  134. init();
  135. if(jump(m/2,n/2,1))
  136. {
  137.   transf(startx,starty);
  138.   output();
  139. }
  140. else cout<<"No!"<<endl;
  141. return 0;
  142. }
複製代碼




歡迎光臨 伊莉討論區 (http://godaddy01.mobile.wahas.com/) Powered by Discuz!