马踏棋盘(C语言版)

2024-07-12 03:56| 来源: 网络整理| 查看: 265

文章目录题目数据定义程序各函数主要思想流程图输出分析源码暴力和简单贪心马踏棋盘是栈的一个十分经典的应用，最基本的完成思路其实就是深度优先搜索(dfs)，是一种十分暴力的处理方式，费时费力还不一定可以得到一个好的结果。使用贪心算法，将每一步，每一步的下一步都进行贪心，便会节省大量的时间，而且成功率十分客观，现就马踏棋盘的一种贪心算法做以下总结

题目

设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋 8x8 棋盘 Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。编制递归或非递归程序，求出马的行走路线，并按求出的行走路线输出。（1）将行走路线以坐标的形式输出。（2）在方阵中输出 1~64 个行走足迹；

数据定义 #include #include #include #define ROW 8 #define COL 8 #define MAX_STEPS ROW*COL //栈结构体 typedef struct stack{ int x_adr; //纵坐标 int y_adr; //横坐标 int direction; //方向 }HORSE_CHESS_STACK; //存储路径棋盘 int chess[ROW+1][COL+1]; //下一步方向 //一号 int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1}, {1,-2},{-1,-2},{-1,2},{1,2}}; //二号 /* int dir[8][2] = {{1,2},{-1,-2},{-2,1},{2,1}, * {2,-1},{1,-2},{-1,2},{-2,-1}}; */ //栈顶 int top; HORSE_CHESS_STACK Adr_Stack[MAX_STEPS]; //出栈次数 int out_stack;

值得注意的是，结构体中，x_adr 其实是真实的纵坐标，y_adr 其实是真实的横坐标（大家画个数组表示的棋盘，其实就懂了）。这个首先要明确，不然在后面的定义和赋值等操作时，会有很多不便。

程序各函数 //初始化数据 void init(); //debug 打印栈的情况 void print_stack(); //入栈 void push_stack(int x_real,int y_real); //出栈 void pop_stack(); //标记位置 void mark_chess(int x,int y); //打印路径 void print_chess_board(); //打印每一步的位置 int t = 1; void print_steps(); //马踏棋盘（贪心）算法 void run_horse_tanxin(); 主要思想

我们算法最核心的部分，是在下一步到底应该如何选择这件事上，主要的贪心思路就是：我们先判断下一步都有哪些位置可以走，然后我们再判断其可走位置的再下一步，有几个位置可以走，并统计这几个末端位置的在下一步有几个位置可以走。也就是分别计算当前位置下下一步的权，之后我们将下下一步的权都加起来，算成下一步的权，并存储到 next 数组里面。之后，我们建立 real_next 数组，通过查找遍历，依次将 next 中最小元素的下标赋值给 real_next 数组，这样，我们就得到了一个下一步走的方向顺序的数组 real_next。这时，我们就可以开始按照 real_next 的顺序来走下一步

以下是核心代码(注释已加)：

//现在位置 x_now = Adr_Stack[top].x_adr; y_now = Adr_Stack[top].y_adr; //对方向进行排序 int next[ROW] = {}; for(int i = 0;i 0 && x_next 0 && y_next {1,2},{-1,-2},{-2,1},{2,1}, {2,-1},{1,-2},{-1,2},{-2,-1}}; */

【本文地址】

马踏棋盘(C语言版)

马踏棋盘(C语言版)

今日新闻

推荐新闻