马的遍历问题
遍历 问题
2023-09-11 14:21:03 时间
题意例如以下:
马的遍历问题。设计程序完毕例如以下要求:
在中国象棋棋盘上,对任一位置上放置的一个“马”.
均能选择一个合适的路线,使得该棋子能按象棋的规则
不反复地走过棋盘上的每一位置。
思路:这是一个DFS搜索,然后没有使用另外的数组来标记某一位置是否已经被走过,而是直接使用存步数的数组num[][]来作为标记数组!
然后我使用了两个数组作为方向坐标,以便能让马移动,同一时候也能记录马所在位置的坐标!(马是能够从8个移动方向中选择的!)
代码还是非常好理解的!
至于棋盘的规格能够自己设定,我这里是使用的8x8的棋盘!
代码例如以下:
/* 马的遍历问题。设计程序完毕例如以下要求: 在中国象棋棋盘上,对任一位置上放置的一个“马”. 均能选择一个合适的路线,使得该棋子能按象棋的规则 不反复地走过棋盘上的每一位置。程序输出8×8方阵. */ #include<cstdio> #include<iostream> #include<cstring> using namespace std; int num[8][8],ans,step,n,m; int xx[8]= {2,1,-1,-2,-2,-1,1,2}; int yy[8]= {1,2,2,1,-1,-2,-2,-1}; bool is_ok(int x,int y) { if(x<0||x>7||y>7||y<0) return false; if(num[x][y])//不等于0表明这个位置已经被走过了! return false; return true; } void print() { ans++; printf("第【%d】个走法:\n",ans); for(int i=0; i<8; i++) { for(int j=0; j<8; j++) printf("%4d",num[i][j]); printf("\n"); } printf("\n"); return ; } void dfs(int x,int y,int step) { for(int i=0; i<8; i++) { int X=xx[i]+x; int Y=yy[i]+y; if(is_ok(X,Y)) { num[X][Y]=step; if(64==step) print(); else dfs(X,Y,step+1); num[X][Y]=0; } } } int main() { int x,y; printf("请输入出发坐标:"); scanf("%d%d",&x,&y); memset(num,0,sizeof(num)); num[x][y]=1; ans=0; dfs(x,y,2); if(!ans) cout<<"没有合适的走法满足要求!\n"; cout<<"到此结束了...\n"; return 0; }
相关文章
- 数据结构:二叉树(前,中,后,层次)非递归遍历。
- Java 目录操作三(在指定目录中查找某字母开头文件、获取系统根目录、获取当前工作目录、遍历目录)
- TypeScript ES6-Promise 递归遍历文件夹中的文件
- 《jQuery Cookbook中文版》——1.9 根据当前上下文遍历DOM获得新的DOM元素集
- java 遍历map对象的四种方式
- 微信小程序中的循环遍历问题
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 已知二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列
- 【Leetcode】105: 从前序与中序遍历序列构造二叉树
- nyoj 77-开灯问题 (倍数遍历)
- [LeetCode] 589. N-ary Tree Postorder Traversal N叉树的后序遍历
- 自引用结构--之创建双向遍历的链表