题目链接：http://poj.org/problem?id=2488
A Knight's Journey
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 52426 | Accepted: 17787 |
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.
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
Source
TUD Programming Contest 2005, Darmstadt, Germany
输出路径的寻路问题
字典序只需要调整方向数组的优先级即可
p行q列，但输出时先输出q所对的坐标，就像给你(x,y),让你输出(y,x),算是小坑。。。（也可能是我太蠢了QAQ）
因为字典序最小，所以第一个一定是A1，即从A1开始
因为已经调整了方向数组的优先级，所以找到的第一个路径就是答案
代码附上：
#include<cstdio> #include<iostream> #include<queue> #include<string> #include<cstring> #define sca(a) scanf("%d",&a ); #define sca2(a,b) scanf("%d%d",&a,&b ); #define sca3(a,b,c) scanf("%d%d%d",&a,&b,&c); #define mem(a,b) memset(a,b,sizeof(a)); #define FOR0(i,j) for(int i=0;i<=j;++i) #define FOR1(i,j) for(int i=1;i<=j;++i) using namespace std; struct node { int x,y,z,step; }; char plat[40][40][40]; int vis[40][40][40]; int dir[6][3]={0,0,1,0,1,0,1,0,0,-1,0,0,0,-1,0,0,0,-1}; int m,n,o; int sx,sy,sz; void ini() { mem(plat,0); mem(vis,0); } int main() { //cout<<sx<<sy<<sz; while(scanf("%d%d%d",&o,&m,&n)&&m+n+o) { ini(); for(int i=1;i<=o;i++) { for(int j=1;j<=m;j++) { scanf("%s", plat[i][j]+1); for(int k=1;k<=n;k++) { if(plat[i][j][k]=='S') { sx=j;sy=k;sz=i; } } } } //cout<<sx<<sy<<sz; queue<node>q; q.push({sx,sy,sz,0}); vis[sz][sx][sy]=1; int flag=0; while(!q.empty()) { node now=q.front(); q.pop(); if(plat[now.z][now.x][now.y]=='E') { flag=1; printf("Escaped in %d minute(s). ", now.step); break; } int nex,ney,nez; for(int i=0;i<6;i++) { nex=now.x+dir[i][0]; ney=now.y+dir[i][1]; nez=now.z+dir[i][2]; if(nex<1||nex>m||ney<1||ney>n||nez<1||nez>o) continue; if(vis[nez][nex][ney]) continue; if(plat[nez][nex][ney]=='.'||plat[nez][nex][ney]=='E') { //printf("%d %d %d ",nex,ney,nez ); vis[nez][nex][ney]=1; q.push({nex,ney,nez,now.step+1}); } } } if(!flag) printf("Trapped! "); } return 0; }