A Knight's Journey
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 66 Accepted Submission(s) : 27
Problem 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
PKU
题意：
给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。经典的“骑士游历”问题。
思路：
1、 题目要求以"lexicographically"方式输出，也就是字典序...要以字典序输出路径，那么搜索的方向（我的程序是path()函数）就要以特殊的顺序排列了...这样只要每次从dfs(A,1)开始搜索，第一个成功遍历的路径一定是以字典序排列...
下图是搜索的次序，马的位置为当前位置，序号格为测试下一步的位置的测试先后顺序
按这个顺序测试，那么第一次成功周游的顺序就是字典序
2、国际象棋的棋盘，行为数字a；列为字母b
这一题一定程度上考验了做题者的模拟思想，利用了DFS+回溯；
AC代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath> using namespace std; int s[][]={};
int number=;
int a;
int b; void path(int &x,int &y,int i,int j,int num)
{
switch(num)
{
case :{x=i-;y=j-;break;}
case :{x=i+;y=j-;break;}
case :{x=i-;y=j-;break;}
case :{x=i+;y=j-;break;}
case :{x=i-;y=j+;break;}
case :{x=i+;y=j+;break;}
case :{x=i-;y=j+;break;}
case :{x=i+;y=j+;break;}
}
return;
} void dfsz(int row,int cow)
{
char c=(char)(cow-+'A');
cout<<c<<row;
if(number==a*b){//当number=a*b的时候则证明输出完毕
return;
}
number++;//自己后的number代表着该输出第number个点了
int x,y;
for(int i=;i<=;i++)//寻找第number个点
{
path(x,y,row,cow,i);
if(s[x][y]==number)
break;
}
dfsz(x,y);//输出（x，y）这个点；
return;
} bool dfs(int row,int cow)//表示行进到了（row，cow）这个点
{
if(row<=||row>a)//横坐标超界
return false;//竖坐标超界
if(cow<=||cow>b)
return false;
if(s[row][cow])//该点已经被访问过
return false;
number++;
s[row][cow]=number;//该点是第number个点
if(number==a*b){//当number=a*b的时候则证明输出完毕
return true;
}
int i;
for(i=;i<=;i++){
int x,y;
path(x,y,row,cow,i);//计算下一步的坐标（x，y）
bool a=dfs(x,y);//判断点（x，y）
if(a){
return true;
}
}
s[row][cow]=;//这一步访问点（row，cow）不行
number--;
return false;
} int main()
{
// freopen("1.txt","r",stdin);
int test;
cin>>test;
int k=;
while(k<=test){
cin>>a>>b;
number=;
memset(s,,sizeof(s));//每一个样例都要初始化，我就在这WA好几次
bool sgin=false;
for(int i=;i<=a;i++){
for(int j=;j<=b;j++){
sgin=dfs(i,j);
if(sgin){
number=;
cout<<"Scenario #"<<k<<":"<<endl;
dfsz(i,j);
cout<<endl<<endl;//输出结束后有一个空行
break;
}
s[i][j]=;
}
if(sgin)
break;
}
if(!sgin){
cout<<"Scenario #"<<k<<":"<<endl<<"impossible"<<endl<<endl;//输出结束后有一个空行，切记！
}
k++;
}
return ;
}