The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?
ProblemFind a path such that the knight visits every square once. The knight can start and end on any square of the board.
InputThe input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 ≤ p * q ≤ 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
OutputThe output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. If no such path exist, you should output impossible on a single line.
Sample Input3 1 1 2 3 4 3
Sample Output
Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4
Source: TUD Programming Contest 2005 Problem ID in problemset: 1702
//比赛的时候自己错了一点,赛后交了是对的,唉,深搜一定要细心啊!!!!
// 639669 2009-05-16 19:27:22 Accepted 1702 C++ 1.7K 0'00.01" 1204K forever4444 // 不打表也是对的 #include < iostream > #include < stack > #define MAX 27 using namespace std; bool used[MAX][MAX],mark; int sum,p,q,t; int a[ 8 ][ 2 ] = {{ - 1 , - 2 },{ 1 , - 2 },{ - 2 , - 1 },{ 2 , - 1 },{ - 2 , 1 },{ 2 , 1 },{ - 1 , 2 },{ 1 , 2 }}; int num; typedef struct node { short num; char ch; node(){}; node( short nn, char ccc) { num = nn; ch = ccc; } }Point; stack < Point > S,RS; Point temp; void Init() { scanf( " %d%d " , & p, & q); int i,j; for (i = 0 ;i < q;i ++ ) for (j = 0 ;j < p;j ++ ) used[i][j] = false ; } bool Bound( int x, int y) { if (x >= 0 && y >= 0 && x < p && y < q) return true ; else return false ; } void DFS( int x, int y, int sum) // x是列,y是行 { int i,j,tx,ty; if (sum == p * q) { mark = true ; return ; } for (i = 0 ;i < 8 ;i ++ ) { tx = x + a[i][ 1 ]; // tx是列 ty = y + a[i][ 0 ]; // ty是行 if ( ! Bound(ty,tx) || used[tx][ty]) { continue ; } used[tx][ty] = true ; S.push(node(ty,( char )( ' A ' + tx))); sum += 1 ; DFS(tx,ty,sum); if ( ! mark) S.pop(); if (mark) return ; used[tx][ty] = false ; sum -= 1 ; } } int main() { int i,j; int zz = 1 ; scanf( " %d " , & t); while (t -- ) { Init(); printf( " Scenario #%d:\n " ,zz ++ ); mark = false ; num = 0 ; for (i = 0 ;i < q;i ++ ) { if (mark) break ; for (j = 0 ;j < p;j ++ ) { used[i][j] = true ; while ( ! S.empty()) S.pop(); sum = 1 ; temp.ch = ( char )( ' A ' + i); temp.num = j; S.push(temp); DFS(i,j,sum); // i是列,j是行 if (mark) break ; used[i][j] = false ; } } if ( ! mark) printf( " impossible\n\n " ); else { while ( ! S.empty()) { temp = S.top(); S.pop(); RS.push(temp); } while ( ! RS.empty()) { temp = RS.top(); RS.pop(); printf( " %c%d " ,temp.ch,temp.num + 1 ); } printf( " \n\n " ); } } return 0 ; }转载于:https://www.cnblogs.com/forever4444/archive/2009/05/16/1458414.html
