View Code of Problem 1005

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<cstring>
#include<algorithm>
using namespace std;

int dir[8][2] = {-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1}; // 8个方向！ 按字典序！
int vis[9][9], path[65][2], s, m ,n;

void dfs(int i, int j, int sum)
{
    if(s)
        return ;
    path[sum][0] = i; 
    path[sum][1] = j;//记录下每次走过的点的行列值
    if(sum == m * n)
    {
        s = 1;
    }
    for(int k = 0; k < 8; k++)
    {
        int dx = i + dir[k][0];
        int dy = j + dir[k][1];
        if(vis[dx][dy] && dx > 0 && dx <= n && dy > 0 && dy <= m)
        {
            vis[dx][dy] = 0;
            dfs(dx,dy,sum + 1);
            vis[dx][dy] = 1;
        }
    }
}

int main()
{
    int t, q = 1, flag = 1, i;
    scanf("%d",&t);
    while(t--)
    {
        if(!flag)
            printf("\n");
        else
            flag = 0;
        scanf("%d%d",&m,&n);//m为列，n为行！反过来搜索方向要改变
        memset(vis, 1, sizeof(vis));
        s = 0;
        vis[1][1] = 0;
        dfs(1,1,1);
        if(s)
        {
            printf("Scenario #%d:\n",q++);
            for(i = 1; i <= m * n; i++)
            {
                printf("%c%d",path[i][0] + 'A' - 1, path[i][1]);//输出
            }
            printf("\n");
        }
        else
        {
            printf("Scenario #%d:\n",q++);
            printf("impossible\n");
        }
    }
}