晕死 就是一个深搜+回朔 很简单 但是一定要注意方向 一定要按题目中给的方向搜索

题目大意：求一个骑士不重复的把所有棋盘上的点都遍历一遍的路径并输出 如果没有就输出impossible

解题思路：8方向的DFS+回朔 其他的看代码注释

code:

#include

using namespace std;

const int N = 27;

int n, m_x, m_y;

int a_x[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };//方向 非常恶心 一定要注意 是字典顺序

int a_y[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };

bool f[N][N];

struct node{

int x, y;

node( int X = 0, int Y = 0 ){ x = X; y = Y; }

}path[N*N+1];//记录路径用的结构体数组

bool isover( int x, int y )//判断越界

{

if( x >= m_x || x <0 || y >= m_y || y < 0 )

   return 1;

return 0;

}

bool dfs( int dip, int x, int y )

{

if( dip == n )

{

   int j;

   for( j = 0; j找到答案则输出路径

   {

    printf( "%c%d", path[j].y+'A', path[j].x+1 );

   }

   cout << endl;

   return true;

}

int i;

for( i = 0; i<8; i++ )

{

   int tx, ty;

   tx = x + a_x[i];

   ty = y + a_y[i];

   if( !isover(tx, ty) && !f[ty][tx] )

   {

    f[ty][tx] = true;

    path[dip].x = tx;

    path[dip].y = ty;

    if( dfs( dip+1, tx, ty ) )

     return true;

    f[ty][tx] = false;//算是回朔吧

   }

}

return false;

}

int main()

{

int cn, cnt;

scanf( "%d", &cn );

for( cnt = 1; cnt <= cn; cnt++ )

{

   scanf( "%d %d", &m_x, &m_y );//A,1

   n = m_x * m_y;

   memset( f, 0, sizeof f );

  

   printf( "Scenario #%d:\n", cnt);

   f[0][0] = true;//标记第一点 只要从A1开始即可。不需要注意：start at any position of the chessboard.

   path[0].y = 0;

   path[0].x = 0;

   if( !dfs( 1, 0, 0 ) )

    printf( "impossible\n" );

   printf("\n");

}

return 0;

}

二、解题思路

使用回溯法进行深度优搜索。

从A1开始搜索，如果能找到一个路径则立即返回，如果从A1出发搜索所有的路径都不能找到一个路径则输出impossible。

注意几个问题：

1、是8个可能的搜索方向的顺序问题。网友贴出来一个顺序是dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

2、不要忘了输出空行。

三、代码

这是一道深搜回溯的题目。我这个新手初次做深搜，浏览了无数大牛的解题报告，收获很大。我原来总以为是要用栈来存储结点，却没想到回溯如此简单。

 1 #include

 2 #include

 3 int n;

 4 int r,c;

 5 int ok;

 6 int visit[100][100];

 7 int px[50],py[50];

 8 int yy[8] = {-1,1,-2,2,-2,2,-1,1};//在这就把输出字典顺序确定了

 9 int xx[8] = {-2,-2,-1,-1,1,1,2,2};

10 

11 int isok(int x,int y)

12 {

13     return x >= 1 && x <= r && y >= 1 && y <= c;

14 }

15 

16 void dfs(int x,int y,int length);

17 int main()

18 {

19     scanf("%d",&n);

20     for(int i =1;i <= n;i++){

21         scanf("%d%d",&c,&r);

22         visit[1][1] = 1;

23         ok = 0;

24         dfs(1,1,1);

25         printf("Scenario #%d:\n",i);

26         if(ok){

27             for(int j = 1;j <= r*c;j++){

28                 printf("%c",px[j]+'A'-1);

29                 printf("%d",py[j]);

30             }

31         }

32         else printf("impossible");

33         printf("\n\n");

34     }

35     system("pause");

36     return 0;

37         

38 }

39 void dfs(int x,int y,int length)

40 {

41     px[length] = x;

42     py[length] = y;

43     if(length == r*c){

44         ok = 1;

45         return;

46     }

47     for(int i = 0;i < 8;i++){

48         int tx = x + xx[i];

49         int ty = y + yy[i];

50         if(isok(tx,ty) && !visit[tx][ty] && !ok){

51             visit[tx][ty] = 1;

52             dfs(tx,ty,length+1);

53             visit[tx][ty] = 0;//巧妙，也是必须的

54         }

55     }

56 }

57