马的哈密尔顿链

马的哈密尔顿链

【问题描述】在一个8×8的国际象棋棋盘上，马（“马走日”）的初始位置(x, y)。怎么走可以不重复地走过每一个格子？这样输出结果：如果马在第i 步落在了格子(s, t)上，则在对应位置输出i。

【贪心策略】每次往出度最小的点上跳。

#include<iostream>

#include<iomanip> #include <cstring>

usingnamespace std;

//两个数组存储对应的偏移量  

const  int stepRow[8] = {-1,-2,-2,-1,1,2,2,1}; const int stepLine[8] =  {-2,-1,1,2,2,1,-1,-2};    int board[8][8];       // 求(i,j)的出口数，各个出口对应的号存在a[]中。      // s表示顺序选择法的开始    int  exitn(int i,int j,int s,int *a)    {   int i1,j1,k,count;          for (count=k=0;k<8;k++)    {        i1 = i + step8[(s + k)% 8];   j1 = j + step8[(s + k)% 8];   if (i1>=0 && i1<8 &&  j1>=0 && j1<8 && board[i1][j1]==0)    a[count++] = (s + k)% 8;    }      return count;    }         // 判断选择下个出口，s  是顺序选择法的开始序号    int  next(int i,int j,int s)    {   int m, kk, a[8], b[8], temp;  if ((m=exitn(i,j,s,a))==0) return -1;     // 没有出口          for (int min=9,k=0; k<m; k++)    {    // 逐个考虑取下一步最少的出口的出口      temp = exitn(i+step8[a[k]], j+step8[a[k]],  s, b);   if (temp<min) min = temp,  kk = a[k];    }      return kk;    }   int main()    {   int i,j,step,no,start=0;          cin>>sx>>sy;    do    {      memset(board,0,sizeof(board));   board[sx][sy] = 1;   i = sx, j = sy;             for (step=2; step<=64; step++)

第四单元 贪心算法

{       no = next(i,j,start)    if (no == -1) break;    i += step8[no], j += step8[no];    board[j] = step;      }       if (step>64 || no==-1) break;   start++;    } while(step<=64);          if (no != -1)        // 输出结果      for (i=0; i<8; i++)      {         for (j=0; j<8; j++)  cout<<setw(4)<<board[j];     cout<<endl;      }      return 0;    }