问题描述:将马随机放在国际象棋的 848 棋盘 Bord[8 118]的某个方格中,马按走棋规 则进行移动。要求每个方格上只进入一次,走遍棋盘上全部64 个方格。编制非递归程序, 求出马的行走路线,并按求出的行走路线,将数宇1,2…,64 依次填入8#0;众8+ 8的方 阵,输出之C++实现
时间: 2024-03-09 09:50:27 浏览: 7
以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 定义棋盘大小
const int BOARD_SIZE = 8;
// 定义棋盘
int board[BOARD_SIZE][BOARD_SIZE] = { 0 };
// 定义马走的8个方向
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
// 判断一个位置是否在棋盘内
bool is_valid(int x, int y) {
if (x < 0 || x >= BOARD_SIZE || y < 0 || y >= BOARD_SIZE) {
return false;
}
return true;
}
// 非递归方式实现马踏棋盘
void knight_tour(int start_x, int start_y) {
stack<pair<int, int>> s;
s.push(make_pair(start_x, start_y));
board[start_x][start_y] = 1;
int pos = 2;
while (!s.empty()) {
int x = s.top().first;
int y = s.top().second;
bool reached = false;
for (int i = 0; i < 8; i++) {
int new_x = x + dx[i];
int new_y = y + dy[i];
if (is_valid(new_x, new_y) && board[new_x][new_y] == 0) {
s.push(make_pair(new_x, new_y));
board[new_x][new_y] = pos;
pos++;
reached = true;
break;
}
}
if (!reached) {
board[x][y] = 0;
s.pop();
pos--;
}
}
}
// 输出结果
void print_board() {
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
// 随机选择一个起始位置
int start_x = rand() % BOARD_SIZE;
int start_y = rand() % BOARD_SIZE;
knight_tour(start_x, start_y);
print_board();
return 0;
}
```
以上代码中,我们首先定义了一个 8x8 的二维数组 `board`,用于表示棋盘,初始值都为 0。然后定义了马走的8个方向的坐标变化数组 `dx` 和 `dy`。接着实现了一个 `is_valid` 函数,用于判断一个位置是否在棋盘内。最后使用非递归方式实现了马踏棋盘算法,将遍历过的位置标记为已访问,并使用栈来记录当前的位置。
最后输出遍历结果,即完成马踏棋盘的行走路线,并按求出的行走路线,将数宇1,2…,64 依次填入8x8的方阵中,并输出。