pku2488 A Knight's Journey

#include<stdio.h>
#include<math.h>

char ans[60];
bool visit[26][26];
int n,m;

bool dfs(int x,int y,int depth)
{
    if(depth==n*m)
    {
        return true;
    }
    for(int j=0;j<m;j++)        //由于按字典顺序访问，则先遍历棋盘的行，后遍历棋盘的列

        for(int i=0;i<n;i++)
        {
            if(!visit[i][j]&&((abs(i-x)==2&&abs(j-y)==1)||(abs(i-x)==1&&abs(j-y)==2)))
            {
                visit[i][j]=1;
                if(dfs(i,j,depth+1))
                {
                    ans[depth*2]='A'+j;
                    ans[depth*2+1]='1'+i;
                    return true;
                }
                visit[i][j]=0;
            }
        }
    return false;
}

int main()
{
    int cases,count=0;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                visit[i][j]=0;
            //骑士能周游棋盘->骑士能从任意一点出发而遍历棋盘，又要求按字典顺序访问，则需从左上角开始遍历

        ans[0]='A';
        ans[1]='1';
        visit[0][0]=1;

        if(count) printf("\n");
        printf("Scenario #%d:\n",++count);
        if(dfs(0,0,1))
        {
            ans[n*m*2]='\0';
            printf("%s\n",ans);
        }
        else printf("impossible\n");
    }
    return 0;
}