马踏棋盘c++
题目
- 马踏棋盘算法，即骑士周游问题。
- 将马放在国际象棋的 8×8 棋盘的某个方格中，马按走棋规则(马走日字)进行移动。
- 每个方格只进入一次，走遍棋盘上全部 64 个方格。
回溯问题模型
特征
- 解组织成树的形式
- 从根节点开始进行深度优先遍历
- 访问节点时进行判断，是否符合条件，符合就继续，否则进行回溯，此节点后的都不用访问(与暴力算法的区别，降低算法复杂度)
模型
代码
- 代码演示的是5*5的棋盘。
- 递归的出口为步数k=棋盘数M*M。
- 递归主函数就是对每一坐标的8种走法进行判断。符合条件就调用递归函数。
- 然后回溯上一步。
- map变量ma记录棋盘上的每一个坐标是否走过。没有走过的，将其坐标加入map中，成为键，值记录第几步。
#include<iostream>
#include<map>
#include<iomanip> //出输格式设定
using namespace std;
struct Pos{//定义坐标点
int x;
int y;
Pos(int x,int y){
this->x=x;
this->y=y;
}
};
int count=0;//记录一共有多少种解法
void show(int M,map<Pos,int>& ma);
//马的8种走法
Pos delta[]={Pos(-1,2),Pos(-1,-2),Pos(1,2),Pos(1,-2),
Pos(2,1),Pos(2,-1),Pos(-2,1),Pos(-2,-1)};
//运算符重载
Pos operator+(Pos a,Pos b){
return Pos(a.x+b.x,a.y+b.y);
}
//马走的步法是否有效，如果出了格子表示bad，即为true
bool outOfBounds(int M,Pos p){
if(p.x<0 || p.x>= M) return true;
if(p.y<0 || p.y>= M) return true;
return false;
}
//自定义变量Pos需要用map，则须重载<，确保Pos能比较大小
bool operator< (Pos a,Pos b){
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
//bool operator<(const Pos& p) const{
//if(this->x !=p.x) return this->x < p.x;
//return this->y < p.y;
//}
bool f(int M,map<Pos,int>& ma,Pos p,int k){
if(k==M*M){
++count;
cout<< count<<endl;
show(M,ma);
return true;
}
for(int i=0;i<8;i++){
Pos p1=p+delta[i];
if(outOfBounds(M,p1)) continue;
if(ma.count(p1)) continue;
ma[p1] = k+1;
f(M,ma,p1,k+1);
ma.erase(p1);
}
return false;
}
void show(int M,map<Pos,int>& ma){
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
cout <<setw(3)<<ma[Pos(i,j)];
}
cout<<endl;
}
cout<<"********************"<<endl;
}
void horse(int M){
map<Pos,int> ma;
Pos p(0,0);
ma[p]=1;
f(M,ma,p,1);
}
int main(){
horse(5);
cout<<"总共有："<<count<<"种走法";
return 0;
}
原文地址：https://blog.csdn.net/qq_37755459/article/details/142338804
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！