Advertisement
andreisophie

Knight's Tour Euristic

Oct 29th, 2019
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. ifstream f("kte.in");
  6. ofstream g("kte.out");
  7.  
  8. int tbl[15][15],k,xs,ys,n,m;
  9. int deplx[]={2,2,1,-1,-2,-2,-1,1}, deply[]={-1,1,2,2,1,-1,-2,-2};
  10.  
  11. void Greedy(int x, int y)
  12. {
  13.     if (k<n*m)
  14.     {
  15.         int xm,ym,pm=9;
  16.         for (int i=0;i<8;i++)
  17.         {
  18.             int xn,yn,p=0;
  19.             xn=x+deplx[i];
  20.             yn=y+deply[i];
  21.             if (xn>0 && xn<=n && yn>0 && yn<=m && tbl[xn][yn]==0)
  22.             {
  23.                 for (int j=0;j<8;j++)
  24.                 {
  25.                     int xnn=xn+deplx[j];
  26.                     int ynn=yn+deply[j];
  27.                     if (xnn>0 && xnn<=n && ynn>0 && ynn<=m && tbl[xnn][ynn]==0)
  28.                         p++;
  29.                 }
  30.                 if (p<pm)
  31.                 {
  32.                     xm=xn;
  33.                     ym=yn;
  34.                     pm=p;
  35.                 }
  36.             }
  37.         }
  38.         tbl[xm][ym]=++k;
  39.         Greedy(xm,ym);
  40.     }
  41. }
  42.  
  43. void afisare()
  44. {
  45.     for (int i=1;i<=n;i++)
  46.     {
  47.         for (int j=1;j<=m;j++)
  48.         {
  49.             if (tbl[i][j]<10)
  50.                 g<<' ';
  51.             g<<tbl[i][j]<<' ';
  52.         }
  53.         g<<'\n';
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59.     f>>n>>m>>xs>>ys;
  60.     tbl[xs][ys]=++k;
  61.     Greedy(xs,ys);
  62.     afisare();
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement