A Knight's Journey

2:A Knight’s Journey
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
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.
输入
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, …
输出
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.
样例输入
3
1 1
2 3
4 3
样例输出
Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
来源 TUD Programming Contest 2005, Darmstadt, Germany
思路
就拿最后的输入4，3来举例好了
从A1开始找，如果设立坐标轴如下

1）如果你的x, y设立如上图，那么字典序就是(-2,-1)开始往后推，因为我们可以看到，从A1开始查找，第一个满足条件的事字典序（1，2），也就是 A 1 + (1, 2) = B3.如果你的x,y和我设立的不一样，那么定义字典序的时候就会不一样，这个要注意。

2）一开始的时候可以直接初始化vis[1][1] = 1;
因为如果没有进行初始化，假设没有初始化第一个vis[1][1]，那么会出现A1-B3-A1的情况。

#include <iostream>
#include <string.h>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;
int go[8][2] = { {-2,-1},{-2, 1}, {-1,-2},{-1,2}, {1,-2},{1,2},{2,-1},{2,1}};
int vis[30][30];
int n,m,flag;
struct node{
    int x,y;
}a[30];

void dfs(int x, int y,int step){
    a[step].x = x;
    a[step].y = y;
    if(step == n * m){
        for(int i = 1; i <= step; i++)
            printf("%c%d",a[i].x-1+'A', a[i].y);
        cout << endl;
        flag = 1;
    }
    if(flag == 1)
        return;
    for(int i = 0; i < 8; i++)
    {
        int y1 = a[step].y + go[i][1];
        int x1 = a[step].x + go[i][0];
        if(x1 >=1 && x1 <= n && y1 >=1 && y1 <= m && !vis[x1][y1] && !flag){
            vis[x1][y1] = 1;
            dfs(x1, y1, step+1);
            vis[x1][y1] = 0;
        }
    }
}

int main() {
    int count;
    cin >> count;
    while(count--){
        mem(vis,0);
        flag = 0;
        cin >> m >> n;
        vis[1][1] = 1;
        dfs(1,1,1);
        if( flag == 0)  cout << "impossible" << endl;
        cout << endl;
    }
    return 0;
}