本文共 1400 字，大约阅读时间需要 4 分钟。

题目大意：给一些棋盘的大小，总格子数不会超过26,。问一个马在棋盘中能不能把整张期盼跑遍，如果能，输出马行走的路线（字典序），如果不能，则输出“impossible”

m*n <= 26...这不是搜索是什么。。。

注意一下输出的时候是按照字典序，先比较字母大小，在比较数字大小。

不要在深搜完之后处理，因为没法处理。在搜索的时候贪心的搜索，现搜号比较小的点，再搜比较大的点，深搜结束的序列就是按照字典序的了。

CODE：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 30using namespace std;const int dx[] = {0,-1,1,-2,2,-2,2,-1,1};const int dy[] = {0,-2,-2,-1,-1,1,1,2,2};int cases;pair
       
         ans[MAX];bool v[MAX][MAX],judge[MAX][MAX];int m,n;bool finished;inline void Initialize();void DFS(int x,int y,int step);int main(){	cin >> cases;	for(int i = 1;i <= cases; ++i) {		scanf("%d%d",&m,&n);		Initialize();		printf("Scenario #%d:\n",i);		ans[1] = make_pair(1,1);		v[1][1] = true;		DFS(1,1,1);		if(!finished)	puts("impossible");		putchar('\n');	}	return 0;}inline void Initialize(){	finished = false;	memset(v,false,sizeof(v));	memset(judge,false,sizeof(judge));	for(int i = 1;i <= m; ++i)		for(int j = 1;j <= n; ++j)			judge[i][j] = true;}void DFS(int x,int y,int step){	if(finished)	return ;	if(step == m * n) {		for(int i = 1;i <= step; ++i)			printf("%c%d",ans[i].second + 'A' - 1,ans[i].first);		putchar('\n');		finished = true;		return ;	}	for(int i = 1;i <= 8; ++i) {		int fx = x + dx[i];		int fy = y + dy[i];		if(judge[fx][fy] && !v[fx][fy]) {			ans[step + 1] = make_pair(fx,fy);			v[fx][fy] = true;			DFS(fx,fy,step + 1);			v[fx][fy] = false;		}	}}
       
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/38984389 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！