棋法马走日用C++编程
时间: 2023-05-31 21:03:12 浏览: 44
#include <stdio.h>
int main() {
char board[9][9] = { // 棋盘初始化
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}
};
int x, y;
printf("请输入马的起始位置(如:3,4):");
scanf("%d,%d", &x, &y);
x--; // 由于数组下标从0开始,所以要减1
y--;
board[x][y] = 1; // 将起始位置标记为已走过
// 马走日算法
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int count = 1; // 记录已经走过的步数
for (int i = 0; i < 8; i++) { // 8个方向
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 9 || ny < 0 || ny >= 9) { // 越界
continue;
}
if (board[nx][ny] != 0) { // 已经走过
continue;
}
board[nx][ny] = 2; // 标记为下一步可走
count++;
}
while (count < 64) { // 一共需要走64步
int min_x = -1, min_y = -1, min_count = 9;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 9 || ny < 0 || ny >= 9) {
continue;
}
if (board[nx][ny] != 2) {
continue;
}
int next_count = 0;
for (int j = 0; j < 8; j++) { // 统计下一步可走的位置数
int nnx = nx + dx[j];
int nny = ny + dy[j];
if (nnx < 0 || nnx >= 9 || nny < 0 || nny >= 9) {
continue;
}
if (board[nnx][nny] != 0) {
continue;
}
next_count++;
}
if (next_count < min_count) { // 找到可走位置最少的位置
min_count = next_count;
min_x = nx;
min_y = ny;
}
}
if (min_x == -1 || min_y == -1) { // 没有可走的位置了,退出循环
break;
}
x = min_x;
y = min_y;
board[x][y] = ++count; // 标记为已走过
for (int i = 0; i < 8; i++) { // 更新下一步可走的位置
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 9 || ny < 0 || ny >= 9) {
continue;
}
if (board[nx][ny] != 0) {
continue;
}
board[nx][ny] = 2;
}
}
// 打印棋盘
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%2d ", board[i][j]);
}
printf("\n");
}
return 0;
}