poj 2488 A Knight's Journey
Description
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 3Sample Output
Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4题意：就是一匹象棋中的马，“日”字走法要遍历全地图tip：深搜 1 #include<iostream> 2 using namespace std; 3 const int Max=25; 4 5 bool visit[Max][Max],output; 6 int visit_num,p,q;///visit_num记录要走的点数 7 char path[2*Max];///path[]记录路径 8 int dx[8]={-2,-2,-1,-1,1,1,2,2}; 9 int dy[8]={-1,1,-2,2,-2,2,-1,1};///字典序 10 11 void dfs(int depth,int x,int y)///深搜 12 { 13 if(depth==visit_num)///搜到最后 14 { 15 for(int i=0;i<2*depth;i++) 16 cout<<path[i]; 17 cout<<endl<<endl; 18 output=true; 19 return; 20 } 21 22 for(int i=0;i<8&&output==false;i++) 23 { 24 25 int new_x=x+dx[i]; 26 int new_y=y+dy[i]; 27 28 if(new_x>0&&new_y>0&&new_x<=q&&new_y<=p&&visit[new_y][new_x]==false) 29 { 30 visit[new_y][new_x]=true; 31 path[2*depth]='A'+new_x-1; 32 path[2*depth+1]='1'+new_y-1; 33 dfs(depth+1,new_x,new_y); 34 visit[new_y][new_x]=false; 35 } 36 } 37 } 38 39 int main() 40 { 41 int n; 42 cin>>n; 43 for(int i=1;i<=n;i++) 44 { 45 cin>>p>>q; 46 cout<<"Scenario #"<<i<<':'<<endl; 47 48 for(int y=1;y<=p;y++) 49 for(int x=1;x<=q;x++) 50 visit[y][x]=false; 51 visit_num=p*q; 52 output=false; 53 visit[1][1]=true; 54 path[0]='A'; 55 path[1]='1'; // 初始化，设A1为首位置（证明如果能走完的话，必存在一条起点为A1的路径） 56 dfs(1,1,1); 57 58 if(output==false) 59 cout<<"impossible\n\n"; 60 } 61 return 0; 62 }
转载于:https://www.cnblogs.com/moqitianliang/p/4727620.html
