复试上机准备之马跳棋 | Patrick's Space

题目要求

假设国际象棋棋盘有 5*5 共 25 个格子。设计一个程序，使棋子从初始位置（棋盘编号 为 1 的位）开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。

（1）输出一个如图 2 的解，左上角为第一步起点。

（2）总共有多少解。

P.S 国际象棋的棋子是在格子中间的。国际象棋中的“马走日”，如下图所示，第一步为[1,1], 第二步为[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此类推。

分析

这是一个常规的回溯题，要注意的就是一共有八个走的方向，在返回的时候记得还原原本的状态值。

一共有 304 解，代码如下：

# include <iostream>

using namespace std;

int arr[5][5] = {0};
int vis_num = 1;
int cnt = 0;

void horse_jump(int x, int y) {
    // 输出走法
    if (vis_num == 25) {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                cout << arr[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl;
        cnt++;
    }

    // 右二下一
    if (x + 2 < 5 && y + 1 < 5 && arr[x + 2][y + 1] == 0) {
        arr[x + 2][y + 1] = ++vis_num;
        horse_jump(x + 2, y + 1);
        // 重置状态
        arr[x + 2][y + 1] = 0;
        --vis_num;
    }
    // 右一下二
    if (x + 1 < 5 && y + 2 < 5 && arr[x + 1][y + 2] == 0) {
        arr[x + 1][y + 2] = ++vis_num;
        horse_jump(x + 1, y + 2);
        // 重置状态
        arr[x + 1][y + 2] = 0;
        --vis_num;
    }
    // 左二上一
    if (x - 2 >= 0 && y - 1 >= 0 && arr[x - 2][y - 1] == 0) {
        arr[x - 2][y - 1] = ++vis_num;
        horse_jump(x - 2, y - 1);
        // 重置状态
        arr[x - 2][y - 1] = 0;
        --vis_num;
    }
    // 左一上二
    if (x - 1 >= 0 && y - 2 >= 0 && arr[x - 1][y - 2] == 0) {
        arr[x - 1][y - 2] = ++vis_num;
        horse_jump(x - 1, y - 2);
        // 重置状态
        arr[x - 1][y - 2] = 0;
        --vis_num;
    }
    // 左二下一
    if (x - 2 >= 0 && y + 1 < 5 && arr[x - 2][y + 1] == 0) {
        arr[x - 2][y + 1] = ++vis_num;
        horse_jump(x - 2, y + 1);
        // 重置状态
        arr[x - 2][y + 1] = 0;
        --vis_num;
    }
    // 左一下二
    if (x - 1 >= 0 && y + 2 < 5 && arr[x - 1][y + 2] == 0) {
        arr[x - 1][y + 2] = ++vis_num;
        horse_jump(x - 1, y + 2);
        // 重置状态
        arr[x - 1][y + 2] = 0;
        --vis_num;
    }
    // 右二上一
    if (x + 2 < 5 && y - 1 >= 0 && arr[x + 2][y - 1] == 0) {
        arr[x + 2][y - 1] = ++vis_num;
        horse_jump(x + 2, y - 1);
        // 重置状态
        arr[x + 2][y - 1] = 0;
        --vis_num;
    }
    // 右一上二
    if (x + 1 < 5 && y - 2 >= 0 && arr[x + 1][y - 2] == 0) {
        arr[x + 1][y - 2] = ++vis_num;
        horse_jump(x + 1, y - 2);
        // 重置状态
        arr[x + 1][y - 2] = 0;
        --vis_num;
    }
}


int main() {
    arr[0][0] = 1;
    horse_jump(0, 0);
    cout << cnt << endl;

    return 0;
}