http://poj.org/problem?id=2488
题意 ： 给你棋盘大小，判断马能否走完棋盘上所有格子，前提是不走已经走过的格子，然后输出时按照字典序排序的第一种路径
思路 ： 这个题吧，有点别扭，再加上要用字典序输出，所以就要用一点小技巧了，自己提前将能输出字典序的那个先写到数组里保存，也就是说，搜索方向要进行特殊的排列，而这样的话，只要每次找的时候从第0行第0列开始找，第一个成功走完所有的格子一定是按字典序排列的，因为只要能走完所有的格子，而字典序最小的就是左上角那个格子，所以，直接从那个开始遍历就行了，如果马是中间那个位置，那就按照那个顺序来遍历即可
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
int dix[] = {-,,-,,-,,-,} ;//按照这个方向进行遍历
int diy[] = {-,-,-,-,,,,} ;
const int maxn = ;
int xx[maxn],yy[maxn] ;
int mark,m,n;
int vis[maxn][maxn] ;
void dfs(int x,int y,int step)
{
int ax,ay ;
vis[x][y] = step ;
if(m*n == step)
{
mark = ;
return ;
}
for(int i = ; i < ; i++)
{
ax = x+dix[i] ;
ay = y+diy[i] ;
if(ax>=&&ax<m&&ay>=&&ay<n&&!vis[ax][ay])
{
xx[step] = ax ;//因为要输出路径，所以要用数组保存
yy[step] = ay ;
dfs(ax,ay,step+);
if(mark)
return;
vis[ax][ay] = ;
}
}
}
void Init()
{
memset(vis,,sizeof(vis)) ;
memset(xx,,sizeof(xx)) ;
memset(yy,,sizeof(yy)) ;
}
int main()
{
int t;
cin>>t;
for(int i = ; i <= t ; i ++)
{
cin>>m>>n;
int step ;
cout<<"Scenario #"<<i<<":"<<endl;
Init() ;
mark = ;
step = ;
xx[] = ;
yy[] = ;
dfs(,,step) ;//从（0,0）点开始遍历
if(mark)
{
for(int k = ; k < m*n ; k++)
printf("%c%d",yy[k]+'A',xx[k]+);
cout<<endl<<endl;
}
if(!mark)
cout<<"impossible"<<endl<<endl;
}
return ;
}