4.马踏棋盘

#include <stdio.h>
#include <stdbool.h>
#define BOARD_SIZE 8
// 马的移动方向，共有8个可能的方向
int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
// 棋盘上的一个位置
typedef struct {
    int x;
    int y;
} Position;
// 判断一个位置是否在棋盘内
bool isValidPosition(int x, int y) {
    return (x >= 0 && x < BOARD_SIZE&& y >= 0 && y < BOARD_SIZE);
}
// 使用广度优先搜索算法找到马踏棋盘的路径
void findKnightTour(Position start) {
    // 创建一个二维数组来表示棋盘，并初始化为-1
    int chessboard[BOARD_SIZE][BOARD_SIZE];
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            chessboard[i][j] = -1;
        }
    }
    // 创建一个队列来存储待处理的位置
    Position queue[BOARD_SIZE * BOARD_SIZE];
    int front = 0;  // 队列的前端指针
    int rear = 0;   // 队列的后端指针
    // 将起始位置加入队列，并在棋盘上标记为0
    queue[rear++] = start;
    chessboard[start.x][start.y] = 0;
    // 使用广度优先搜索遍历棋盘
    while (front != rear) {
        // 出队一个位置
        Position current = queue[front++];
        // 尝试移动马的位置
        for (int i = 0; i < 8; i++) {
            int nextX = current.x + dx[i];
            int nextY = current.y + dy[i];
            // 判断下一个位置是否合法且未被访问过
            if (isValidPosition(nextX, nextY) && chessboard[nextX][nextY] == -1) {
                // 更新下一个位置的步数，并将其加入队列
                chessboard[nextX][nextY] = chessboard[current.x][current.y] + 1;
                Position next = { nextX, nextY };
                queue[rear++] = next;
            }
        }
    }
    // 打印马踏棋盘的路径
    printf("马踏棋盘的路径为：\n");
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            printf("%2d ", chessboard[i][j]);
        }
        printf("\n");
    }
}
int main() {
    Position start = { 0, 0 };  // 设置起始位置为棋盘的左上角
    findKnightTour(start);
    return 0;
}