POJ 2488 A Knight's Journey

分析：简单DFS，注意字典序最小
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };
 5 const int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
 6 const int MAXN = 30;
 7 
 8 struct point
 9 {
10     int x, y;
11 };
12 
13 bool vis[MAXN][MAXN];
14 point path[MAXN];
15 int p, q;
16 int all;
17 
18 bool check( int& x, int& y )
19 {
20     return ( x >= 0 && x < p && y >= 0 && y < q );
21 }
22 
23 bool DFS( int x, int y, int num )
24 {
25 //    printf("x=%d y=%d num=%d\n", x, y, num);
26 
27     path[num - 1].x = x;
28     path[num - 1].y = y;
29 
30     if ( num == all )
31         return true;
32 
33     vis[x][y] = true;
34 
35     for ( int i = 0; i < 8; i++ )
36     {
37         int xx = x + dx[i];
38         int yy = y + dy[i];
39         if ( check( xx, yy ) && !vis[xx][yy] )
40         {
41             if ( DFS( xx, yy, num + 1 ) ) return true;
42         }
43     }
44 
45     vis[x][y] = false;
46 
47     return false;
48 }
49 
50 int main()
51 {
52     int T, tt = 0;
53 //    freopen( "s.txt", "w", stdout );
54     scanf( "%d", &T );
55     while ( T-- )
56     {
57         scanf( "%d%d", &p, &q );
58         all = p * q;
59         bool flag = false;
60         for ( int j = 0; j < q; j++ )
61         {
62             for ( int i = 0; i < p; i++ )
63             {
64                 memset( vis, false, sizeof(vis) );
65                 if ( DFS(i, j, 1) )
66                 {
67                     flag = true;
68                     break;
69                 }
70             }
71             if ( flag ) break;
72         }
73 
74         printf( "Scenario #%d:\n", ++tt );
75 
76         if ( flag )
77         {
78             for ( int i = 0; i < all; i++ )
79                 printf("%c%d", path[i].y + 'A', path[i].x + 1 );
80             putchar('\n');
81         }
82         else puts("impossible");
83         putchar('\n');
84     }
85     return 0;
86 }