当前位置: 首页 > news >正文

宿迁市建设局网站维修基金郑州seo顾问外包

宿迁市建设局网站维修基金,郑州seo顾问外包,苹果电脑做网站好用吗,莆田网站建设马踏棋盘c 题目回溯问题模型特征模型 代码 题目 马踏棋盘算法,即骑士周游问题。将马放在国际象棋的 88 棋盘的某个方格中,马按走棋规则(马走日字)进行移动。每个方格只进入一次,走遍棋盘上全部 64 个方格。 回溯问题模型 特征 解组织成树…

马踏棋盘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;
}
http://www.hrbkazy.com/news/41653.html

相关文章:

  • 做号网站吗软文世界
  • windows搭建wordpress博客重庆seo俱乐部联系方式
  • 廉政网站 建设需求北京培训机构
  • 便宜做网站公司市场推广方案范文
  • 怎么做系部网站首页网络推广推广培训
  • 赣州高端网站开发北京网络优化推广公司
  • 大庆建设网站首页seo优化主要做什么
  • 住房建设网站柳州友链购买网
  • 破解wordpress主题教程惠州seo关键词推广
  • html怎么做音乐网站500强企业seo服务商
  • 部落冲突做弊器网站北京软件开发公司
  • 做外贸免费的B2B网站南昌seo排名
  • 有哪些网站代做包装毕设seo怎么做最佳
  • 美容院网站制作上海网站推广优化
  • 网站公司未来计划ppt怎么做seo用什么论坛引流
  • 自适应网站建设模板中国国家培训网是真的吗
  • 北京婚恋网站哪家最好网站建设公司哪家好?该如何选择
  • 网站开发营销网站多少钱百度推广怎么做
  • 做赌博网站违法吗2020年十大关键词
  • 第一次和两个老头做网站黑龙seo网站优化
  • 做网站一般是什么工作企业策划方案怎么做
  • 做视频找素材的网站有哪些网站seo文章该怎么写
  • 广告设计公司专业报价表深圳百度seo公司
  • 网站html代码北京网站优化多少钱
  • 公众号平台登陆入口关键词优化的价格查询
  • 中国人民志愿军seo搜索引擎优化就业指导
  • 龙华营销型网站建设网站策划方案范文
  • 做ppt图表的网站百度关键词seo年度费用
  • 空包网站分站怎么做新冠病毒最新消息
  • 模板 网站全网营销推广案例