poj 2488

http://poj.org/problem?id=2488

题意：就是让马把棋盘都走完，每一个点都要走到，出口就是a,b。

#include <stdio.h>
#include <string.h>

int dic[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};  //这个是所走的方向。
int a,b,judge;
int path[30][2],vis[10][10];   //path代表路径，vis代表是否走过这个点，因为每个点只允许走一次。

void dfs(int x,int y,int k)
{
    if(k==a*b){   //走完了
        for(int i=0;i<k;i++)
        {
            printf("%c%d",path[i][0]+'A',path[i][1]+1);  
        }
        printf("
");
        judge=1;
    }
    else {
        for(int i=0;i<8;i++)   //八个方向，依次走
        {
            int n=x+dic[i][0];
            int m=y+dic[i][1];
            if(n>=0&&n<b&&m>=0&&m<a&&!vis[n][m]&&!judge)
            {
                vis[n][m]=1;                
                path[k][0]=n;path[k][1]=m;
                dfs(n,m,k+1);
                vis[n][m]=0;    //一种回溯。
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int q=1;q<=n;q++)
    {
        scanf("%d%d",&a,&b);
        memset(path,0,sizeof(path));
        memset(vis,0,sizeof(vis));
        judge=0;
        path[0][0]=0;
        path[0][1]=0;
        vis[0][0]=1;
        printf("Scenario #%d:
",q);
        dfs(0,0,1);
        if(!judge) printf("impossible
");
        printf("
");
    }
    return 0;
}