sicily 马周游问题

数据量是8*8的了，要做个优化，尽量往分支少的方向搜
马周游的问题，很经典的深搜。以后自己当做模版思路吧
 1 #include<iostream>
 2 #include<memory.h>
 3 #include<vector>
 4 #include<algorithm> 
 5 using namespace std;
 6 
 7 int road[64];
 8 bool vis[8][8];
 9 int change[]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
10 
11 struct Node
12 {
13     int x,y,num;
14     Node(int a,int b)
15     {
16         x = a;
17         y = b;
18         num = 0;
19         for(int i=0;i<16;i+=2)
20         {
21             int now_row=a+change[i];
22             int now_col=b+change[i+1];
23             if(now_row>=0&&now_row<8&&now_col>=0&&now_col<8&&vis[now_row][now_col]==0)  num++;
24             
25         }
26     }
27 };
28 
29 bool cmp(Node a,Node b)
30 {
31     return a.num<b.num;
32 }
33 bool dfs(int row,int col,int cur)
34 {
35     road[cur]=8*row+col+1;
36     if(cur==63) return 1;          //这一句很重要，是深搜的标记结束的地方。说明什么条件下要结束深搜 
37     vector<Node> v;   
38     for(int i=0;i<16;i+=2)
39     {
40         int now_row=row+change[i];
41         int now_col=col+change[i+1];
42         if(now_row>=0&&now_row<8&&now_col>=0&&now_col<8&&vis[now_row][now_col]==0)
43         {
44             Node p(now_row,now_col);
45             v.push_back(p);
46         }
47     }
48     sort(v.begin(),v.end(),cmp);
49     for(int i=0;i<v.size();i++)
50     {
51         Node r=v[i];
52         if(r.num>0||cur==62){      //一下几行是深搜的典型写法 
53 vis[row][col]=1;
54             if(dfs(r.x,r.y,cur+1))
55                 return 1;            //其实深搜的递归不必想太多，从逻辑上想就好。这里是搜索行的话就return 1,不行的话就当没搜过 
56             else vis[row][col]=0;  
57         } 
58     }
59     return 0;  //能执行到这一步说明这条路径是不行的了，return 0 
60 }
61 int main()
62 {
63     int N;
64     while(cin>>N&&N!=-1)
65     {
66         memset(vis,0,sizeof(vis));
67         memset(road,0,sizeof(road));
68         int row=(N-1)/8;
69         int col=(N-1)%8;
70         int current=0;
71         vis[row][col]=1;
72         dfs(row,col,current);
73         for(int i=0;i<64;i++) cout<<road[i]<<' ';
74     } 
75 }