toj 1702 A Knight's Journey

Time Limit: 1.0 Seconds Memory Limit: 65536K Multiple test files

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 ≤ p * q ≤ 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.

Sample Input

Sample Output

Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Source: TUD Programming Contest 2005

Problem ID in problemset: 1702

Submit Back Runs Statistics Clarifications

//639397 2009-05-16 16:21:32 B C 1.2K 0'00.00" 668K forever4444
//#include <stdio.h>
int t;
int main()
{
    scanf("%d",&t);
    int p,q,zz=1;
    while(t--)
    {
        scanf("%d%d",&p,&q);
        printf("Scenario #%d:\n",zz++);
        if(p==1&&q==1)
            printf("A1\n");
        else if(p==3&&q==4)
            printf("A1C2A3B1D2B3C1A2C3D1B2D3\n");
        else
            if(p==3&&q==7)
            printf("A1B3D2F1G3E2G1F3E1G2E3C2A3B1C3A2C1D3B2D1F2\n");
        else if(p==3&&q==8)
            printf("A1B3C1A2C3D1B2D3E1G2E3C2A3B1D2F1H2F3G1E2G3H1F2H3\n");
        else
            if(p==4&&q==3)
            printf("A1B3C1A2B4C2A3B1C3A4B2C4\n");
        else
            if(p==4&&q==5)
            printf("A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4\n");
        else
            if(p==4&&q==6)
            printf("A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1\n");
        else
            if(p==5&&q==4)
            printf("A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5\n");
        else
            if(p==5&&q==5)
            printf("A1B3A5C4A3B1D2E4C5A4B2D1C3B5D4E2C1A2B4D5E3C2E1D3E5\n");
        else
            if(p==6&&q==4)
            printf("A1B3A5C6D4B5D6C4D2B1A3C2B4A2C1D3B2D1C3D5B6A4C5A6\n");
        else
            if(p==7&&q==3)
            printf("A1B3C1A2C3B1A3C2B4A6C7B5A7C6A5B7C5A4B2C4B6\n");
        else
            if(p==8&&q==3)
            printf("A1B3C1A2B4C2A3B1C3A4B2C4A5B7C5A6B8C6A7B5C7A8B6C8\n");
        else
            printf("impossible\n");
        printf("\n");
    }
    return 0;
}

//比赛的时候自己错了一点,赛后交了是对的,唉,深搜一定要细心啊!!!!

//639669 2009-05-16 19:27:22 Accepted 1702 C++ 1.7K 0'00.01" 1204K forever4444
//不打表也是对的
#include <iostream>
#include <stack>
#define MAX 27
using namespace std;
bool used[MAX][MAX],mark;
int sum,p,q,t;
int a[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
int num;
typedef struct node
{
    short num;
    char ch;
    node(){};
    node(short nn,char ccc)
    {
        num=nn;
        ch=ccc;
    }

}Point;
stack<Point>S,RS;
Point temp;
void Init()
{
    scanf("%d%d",&p,&q);
    int i,j;
    for(i=0;i<q;i++)
        for(j=0;j<p;j++)
            used[i][j]=false;
}
bool Bound(int x,int y)
{
    if(x>=0&&y>=0&&x<p&&y<q)
        return true;
    else
        return false;
}
void DFS(int x,int y,int sum) //x是列,y是行
{
    int i,j,tx,ty;
    if(sum==p*q)
    {
        mark=true;
        return;
    }
    for(i=0;i<8;i++)
    {
        tx=x+a[i][1];  //tx是列
        ty=y+a[i][0];   //ty是行
        if(!Bound(ty,tx)||used[tx][ty])
        {
            continue;
        }
        used[tx][ty]=true;
        S.push(node(ty,(char)('A'+tx)));
        sum+=1;
        DFS(tx,ty,sum);
        if(!mark)
            S.pop();
        if(mark)
            return ;
        used[tx][ty]=false;
        sum-=1;
    }
}
int main()
{
    int i,j;
    int zz=1;
    scanf("%d",&t);
    while(t--)
    {
        Init();
        printf("Scenario #%d:\n",zz++);
        mark=false;
        num=0;
        for(i=0;i<q;i++)
        {
            if(mark)
                break;
            for(j=0;j<p;j++)
            {
                used[i][j]=true;
                while(!S.empty())
                    S.pop();
                sum=1;
                temp.ch=(char)('A'+i);
                temp.num=j;
                S.push(temp);
                DFS(i,j,sum);  //i是列,j是行
                if(mark)
                    break;
                used[i][j]=false;
            }
        }
        if(!mark)
            printf("impossible\n\n");
        else
        {
            while(!S.empty())
            {
                temp=S.top();
                S.pop();
                RS.push(temp);
            }
            while(!RS.empty())
            {
                temp=RS.top();
                RS.pop();
                printf("%c%d",temp.ch,temp.num+1);
            }
            printf("\n\n");
        }
    }
    return 0;
}