学步园

//经典的深度优先搜索，必须剪枝才能通过，而且剪枝策略十分神奇，先走下一步可行拓展数最少的，看了大牛的题解才会的<br /> //也就是说假如当前结点有8个可以走的拓展点，对每个可行拓展点再计算它的可行拓展数，然后排序，先走那个可行拓展数最小的<br /> //就是先走那个最没前途的点，这样会更快，因为它这么没前途，要从其它点到达它就更难了，所以先走<br /> #include<iostream><br /> #include<cstring><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;<br /> int dir[8][2] = {-1,-2,-1,2,-2,1,-2,-1,1,2,1,-2,2,1,2,-1};<br /> bool vis[64];<br /> int ans[64];<br /> bool legal(int x,int y)<br /> {<br /> if(x < 0 || x > 7 || y < 0 || y > 7) return false;<br /> return true;<br /> }<br /> int cal_ok(int x,int y)//计算当前结点的可行可拓展数<br /> {<br /> int cnt = 0;<br /> for(int i = 0;i < 8;++i)<br /> {<br /> int X = x + dir[i][0];<br /> int Y = y + dir[i][1];<br /> if(legal(X,Y) && !vis[X+Y*8])<br /> ++cnt;<br /> }<br /> return cnt;<br /> }<br /> struct coord<br /> {<br /> int x,y;<br /> int cnt;<br /> coord(int X,int Y)<br /> { x = X; y = Y; cnt = cal_ok(X,Y); }//cnt记录可行拓展数<br /> };<br /> bool cmp(coord a,coord b)<br /> {<br /> return a.cnt < b.cnt;<br /> }<br /> bool dfs(int x,int y,int cur)//将DFS函数定义为BOOL型，一旦递归成功搜索到解，那么直接通过if函数一层层return回来<br /> {<br /> vector<coord> v;<br /> vis[y*8+x] = 1;<br /> ans[cur] = y*8 + x + 1;<br /> if(cur == 63) return true;<br /> for(int i = 0;i < 8;++i)<br /> {<br /> int X = x + dir[i][0];<br /> int Y = y + dir[i][1];<br /> if(legal(X,Y) && !vis[X+Y*8])<br /> v.push_back(coord(X,Y));//构造函数中带有计算可行拓展数<br /> }<br /> sort(v.begin(),v.end(),cmp);<br /> for(int i = 0;i < v.size();++i)<br /> {<br /> if(dfs(v[i].x,v[i].y,cur + 1))<br /> return true;//拓展成功，跳出当前层<br /> }<br /> vis[y*8+x] = 0;<br /> return false;//当前结点拓展失败<br /> }<br /> int main()<br /> {<br /> int n;<br /> while(scanf("%d",&n) && n != -1)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> dfs((n-1) % 8,(n-1)/8,0);<br /> printf("%d",ans[0]);<br /> for(int i = 1;i < 64;++i)<br /> printf(" %d",ans[i]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }