poj 2488A Knight's Journey (dfs)

Background  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?  Problem  Find a path such that the knight visits every square once. The knight can start and end on any square of the board. Input The 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, . . . Output The 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 Input 3 1 1 2 3 4 3 Sample Output Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4

这道题问字典序最小的路径，只要从（0,0）开始找就可以了，因为如果存在一条路径那么一定是通路，一定从（0,0）开始，直接dfs+回溯，注意下一步转移的路的方向

输出路径时用循环，递归易超时；

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <string> #include <queue> #include <vector> using namespace std; typedef long long LL; const int N = 1000; const int mod = 100000000; int dir[8][2]= {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}}; int vis[30][30], pre[30]; struct node { int x, y; } path[N]; int n, m, flag; void dfs(int s, int e,int step) { if(flag||step>n*m+1) return ; if(step==n*m+1) { for(int i=1; i<=n*m; i++) printf("%c%d",('A'+path[i].y), path[i].x+1); flag=1; return ; } for(int i=0; i<8; i++) { int a=s+dir[i][0], b=e+dir[i][1]; if(a<0||a>=n||b<0||b>=m||vis[a][b]) continue; vis[a][b]=1, path[step].x=a, path[step].y=b; dfs(a,b,step+1); vis[a][b]=0; } return ; } int main() { int t, ncase=1; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); printf("Scenario #%d:\n",ncase++); flag=0; memset(vis,0,sizeof(vis)); vis[0][0]=1, path[1].x=0, path[1].y=0; dfs(0,0,2); if(flag!=1) printf("impossible"); printf("\n\n"); } return 0; }