大意:
给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。
1 #include <map> 2 #include <stack> 3 #include <queue> 4 #include <math.h> 5 #include <stdio.h> 6 #include <string.h> 7 #include <iostream> 8 #include <limits.h> 9 #include <algorithm> 10 #define LL long long 11 #define min(a,b) (a>b?b:a) 12 #define max(a,b) (a>b?a:b) 13 #define eps 1e-9 14 #define INF 1 << 30 15 using namespace std; 16 17 bool vis[30][30], output; 18 int Num; 19 char path[120]; 20 int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; 21 int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; 22 int a, b; 23 24 void Dfs(int depth, int x, int y) 25 { 26 if(depth == Num) 27 { 28 for(int i = 0; i < 2*depth; i++) 29 printf("%c", path[i]); 30 printf(" "); 31 output = true; 32 return ; 33 } 34 for(int i = 0; i < 8 && output == false; i++) 35 { 36 int new_x = x+dx[i]; 37 int new_y = y+dy[i]; 38 if(new_x >= 1 && new_x <= b && new_y >= 1 && new_y <= a && vis[new_y][new_x] == false) 39 { 40 vis[new_y][new_x] = true; 41 path[2*depth] = 'A'+new_x-1; 42 path[2*depth+1] = '1'+new_y-1; 43 Dfs(depth+1, new_x, new_y); 44 vis[new_y][new_x] = false; 45 } 46 } 47 } 48 49 void run() 50 { 51 int n; 52 scanf("%d", &n); 53 for(int p = 1; p <= n; p++) 54 { 55 scanf("%d%d", &a, &b); 56 printf("Scenario #%d: ", p); 57 for(int i = 1; i <= a; i++) 58 for(int j = 1; j <= b; j++) 59 vis[i][j] = false; 60 Num = a*b; 61 output = false; 62 vis[1][1] = true; 63 path[0] = 'A'; 64 path[1] = '1'; 65 Dfs(1, 1, 1); 66 if(output == false) 67 printf("impossible "); 68 } 69 } 70 71 int main(void) 72 { 73 run(); 74 75 return 0; 76 }