POJ2488A Knight's Journey

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  ;

}