POJ 2488 A Knight's Journey

 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
", 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:
", ++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('
');

81         }

82         else puts("impossible");

83         putchar('
');

84     }

85     return 0;

86 }