sicily 1153. 马的周游问题

一、题目描述

在一个8 * 8的棋盘中的某个位置有一只马，如果它走29步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，找出它的一条周游路线。

为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48

49 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64

马的走法是“日”字形路线，例如当马在位置15的时候，它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的，例如从位置1只能到达9和14。

Input

输入有若干行。每行一个整数N(1<=N<=30)，表示马的起点。最后一行用-1表示结束，不用处理。

Output

对输入的每一个起点，求一条周游线路。对应地输出一行，有30个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。

Sample Input

-1

Sample Output

注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。

二、算法思想及主要数据结构

算法思想：这题使用 dfs 来找到一条路径，因为根据题目描述可以看出路径的深度并不会很大，所以采用深搜是一种比较好的方法。使用递归来达到深搜。
主要数据结构：这里使用结构体来保存节点内部值，使用 vector 来保存节点。

三、详细解题思路

首先因为棋盘的大小变大了，这个时候完全不剪枝的深搜显然会超时。根据树的结构可以知道，减少上层子节点，则下层子节点数也会相应减少。所以这里的一个思路就是保证先走可扩展位置比较少的位置，可扩展就是说如果当前节点是该节点，那么其可以走的下一个节点的数目。所以这里先求得下一个可能走的节点的可扩展位置数，然后根据位置数进行一个排序，优先走位置数较少的位置。

2. 位置处理，因为原棋盘的位置表示是用一个数字来表示的，这样对于我们的操作并不适合，所以将棋盘的代表数字转成一个 8 * 8 数组的下标来处理：

x = (N - 1) / 8;

y = (N - 1) % 8;

3. 马的移动分析：因为马必须走“日”型的路线，所以马的最多移动位置会有 8 个，分别是如下：

position(-1, 2), position(-2, 1), position(-2, -1), position(-1, -2),

position(1, -2), position(2, -1), position(2, 1), position(1, 2)

那么在每次移动后都可能有 8 个位置，需要对这些位置进行有效性判断：

bool isValid(int x, int y) {

return x >= 0 && y >= 0 && x <= 7 && y <= 7;

}

也即位置一定要在棋盘内。

4. 路径记录：因为一定会在 64 步内得到结果，那么也就是说每一步代表一个位置，那么只需要用一个含 64 个元素的数组来记录位置就可以。

int route[64];

在走一条新的路径的时候，只需要将步数对应位置的数字改成对应新位置的数字就可以：

route[step] = 8 * yTemp + xTemp + 1;

5. 在每个当前位置，会取得其可能走的下一个位置，在得到这些位置后再一这些位置为当前节点去看其可能的扩展位置的数目，根据这个数目进行排序，保存在一个vector里面，然后从该 vector 里面找下一个位置即可

if (isValid(xTemp, yTemp)) {

int canMovePoisitionNum = getCanMovePositionNum(xTemp, yTemp);

if (canMovePoisitionNum != 0)

poisition.push_back(Position(xTemp, yTemp, canMovePoisitionNum));

}

sort(poisition.begin(), poisition.end(), cmp);

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool visited[8][8];
bool success = false;
int roate[64];

struct Position{
    Position(int x_ = 0, int y_ = 0, int num = 0): x(x_), y(y_), canMovePoisitionNum(num) { }                     
    int x;
    int y;
    int canMovePoisitionNum;
};
 
Position Move[8] = {Position(1, -2), Position(2, -1), Position(2, 1), Position(1, 2),
                    Position(-1, 2), Position(-2, 1), Position(-2, -1), Position(-1, -2)};


bool isValid(int x, int y) {
    return x >= 0 && y >= 0 && x <= 7 && y <= 7;
}

int getCanMovePositionNum(int x, int y) {
    int canMovePoisitionNum = 0;
    for (int i = 0; i != 8; ++i) {
        if(isValid(x + Move[i].x, y + Move[i].y))
            canMovePoisitionNum++;
    }
    return canMovePoisitionNum;
}

bool cmp(const Position &a, const Position &b) {
    return a.canMovePoisitionNum < b.canMovePoisitionNum;
}

void search(int step, int x, int y) {
    vector<Position> poisition;
    for (int i = 0; i != 8; ++i) {
        int xTemp = x + Move[i].x;
        int yTemp = y + Move[i].y;
        if (isValid(xTemp, yTemp)) {
            int canMovePoisitionNum = getCanMovePositionNum(xTemp, yTemp);
            if (canMovePoisitionNum != 0)
                poisition.push_back(Position(xTemp, yTemp, canMovePoisitionNum));
        }
    }
    sort(poisition.begin(), poisition.end(), cmp);
    for (int i = 0; i != poisition.size(); ++i) {
        if (success)
            return;
        if (step == 63) {
            success = true;
            return;
        }
        if (!visited[poisition[i].x][poisition[i].y]) {
            ++step;
            roate[step] = 8 * poisition[i].x + poisition[i].y + 1;
            visited[poisition[i].x][poisition[i].y] = true;
            search(step, poisition[i].x, poisition[i].y);
            visited[poisition[i].x][poisition[i].y] = false;
            --step;
        }
    }
}

int main(int argc, char *argv[])
{
    int N, x, y;
    while (scanf("%d", &N) && N != -1) {
        roate[0] = N;
        memset(visited, false, sizeof(visited));
        success = false;
        x = (N - 1) / 8;
        y = (N - 1) % 8;

        visited[x][y] = true;
        search(0, x, y);

        for (int i = 0; i != 63; i++)
            printf("%d ", roate[i]);
        printf("%d
", roate[63]);
    }

    return 0;
}