马的Hamilton周游路线问题
思路：
马走日字，每一步有8个方向可以选择，利用回溯穷举8个方向进行尝试即可，直到找到答案，搜索停止，exit(1)进行退出，不然结果不唯一，且指数级的复杂度，分分钟爆掉。
至于书中给的N,M可能很大，这时候我们会用到分治法。
分治算法在计算过程中必须依赖一些事先计算好的少量数据，所以必须通过回溯用O(1)的时间内计算6*6，6*8，8*8，8*10，10*10，10*12的结构化棋盘。（因为这些棋盘的规模与N无关，可以事先计算好）
至于N,M较大时如何进行divide和conquer自己思考一下。
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <iostream> #include <queue> using namespace std; int N,M; int a[100][100]; struct Node{ int x; int y; }; Node Q[10005]; //定义马走的8个方向 int dir_x[8] = {-1,-2,-2,-1,1,2,2,1}; int dir_y[8] = {2,1,-1,-2,-2,-1,1,2}; void print(){ for(int i=0; i<N; i++){ for(int j=0; j<M; j++) printf("(%d,%d) ",Q[i*N+j+1].x,Q[i*N+j+1].y); printf("\n"); } cout << endl << endl; for(int i=0; i<N; i++){ for(int j=0; j<M; j++) printf("%-3d ",a[i][j]); printf("\n"); } } bool judge(int x,int y){ for(int i=0; i<8; i++){ if( x+dir_x[i]==0 && y+dir_y[i]==0 ) return true; } return false; } void DFS(int cur_x,int cur_y,int step){ if(step==N*M+1 && judge(cur_x,cur_y)){ print(); exit(1);//exit是退出整个进程,exit里面的参数是作为进程的返回值提供给操作系统 } int tmp_x,tmp_y; for(int i=0; i<8; i++){ tmp_x = cur_x+dir_x[i]; tmp_y = cur_y+dir_y[i]; if( tmp_x<0 || tmp_x>=N || tmp_y<0 || tmp_y>=M || a[tmp_x][tmp_y]!=0) continue; Q[step].x = tmp_x; Q[step].y = tmp_y; a[tmp_x][tmp_y] = step; DFS(tmp_x,tmp_y,step+1); a[tmp_x][tmp_y] = 0; } } int main(){ scanf("%d %d",&N,&M); a[0][0] = 1; Q[1].x = 0; Q[1].y = 0; DFS(0,0,2); return 0; } 分享2个解题链接：http://blog.csdn.net/crayondeng/article/details/17174951
http://blog.sina.com.cn/s/blog_7e9a88f70100zj3h.html
