Sicily 1153: 马的周游问题（DFS+剪枝）

　　这道题没有找到一条回路，所以不能跟1152一样用数组储存后输出。我采用的方法是DFS加剪枝，直接DFS搜索会超时，优化的方法是在搜索是优先走出度小的路径，比如move1和move2都可以走，但是如走了move1后下一步有7种方向可以走，而走了move2后有2种方向可以走，那我们就优先走move2，具体实现参考代码：

 #include<bits/stdc++.h>

 using namespace std;

 int _move[][] ={{, -}, {, -}, {, }, {, },{-, }, {-, }, {-, -}, {-, -}};

 struct Node{

     int x, y;

     vector<int>path;

 };

 Node node;

 struct Move{

     int x, y;

     int degree;

 };

 void getDegree(Move &move){

     int ans = ;

     int cur_x = node.x+ move.x;//下一步的位置

     int cur_y = node.y + move.y;

     for(int i = ; i < ; i++){//以cur_x, cur_y为起点，检查其出度

         int x = cur_x + _move[i][];

         int y = cur_y + _move[i][];

         if( <= x && x <  &&  <= y && y < ){//如果坐标没有越界并且没有重复走过，则出度加一

             int flag = ;

             for(int j = ; j < node.path.size(); j++){

                 if(node.path[j] == x* + y){

                     flag = ;

                     break;

                 }

             }

             if(flag)ans++;

         }

     }

     move.degree = ans;

 }

 bool cmp(Move m1, Move m2){

     return m1.degree < m2.degree;

 }

 bool dfs(int x, int y){

     node.x = x;

     node.y = y;

     Move move[];

     for(int i = ; i < ; i++){

         move[i].x = _move[i][];

         move[i].y = _move[i][];

         if( <= node.x + _move[i][] && node.x + _move[i][] <  &&

             <= node.y + _move[i][] && node.y + _move[i][] < )

             getDegree(move[i]);    //如果下一步没有越界，则获取它的出度

         else move[i].degree = ; //若下一步越界，出度设为100

     }

     sort(move, move+, cmp);//对出度从小到大排序

     for(int i = ; i < ; i++){

             if(move[i].degree == ) continue;//若出度为100，跳过

             int x = node.x + move[i].x;//下一步位置

             int y = node.y + move[i].y;

             if( <= x && x <  &&  <= y && y < ){

                 int flag = ;

                 for(int j = ; j < node.path.size(); j++){

                     if(node.path[j] == x* + y){

                         flag = ;

                         break;

                     }

                 }

                 if(flag){

                     node.path.push_back(x* + y);//走下一步

                     if(node.path.size() >= ){//当path的size等于64，则说明已经走遍

                         for(int i = ; i < node.path.size(); i++){

                             cout << node.path[i] +  << ' ';

                         }

                         cout << endl;

                         return true;

                     }

                     if(dfs(x, y))return true;

                     node.path.pop_back();//还原到原来

                     node.x -= move[i].x;

                     node.y -= move[i].y;

                 }

             }

     }

     return false;

 }

 int main(){

     int n;

     while(cin >> n && n != -){

         node.path.clear();

         n = n-;

         int a = n / ;

         int b = n % ;

         node.path.push_back(a* + b);

         dfs(a, b);

     }

 }