怎么创建网站论坛,淘宝网站建设目的,wordpress网页加速,wordpress调试模式马踏棋盘c 题目回溯问题模型特征模型 代码 题目
马踏棋盘算法#xff0c;即骑士周游问题。将马放在国际象棋的 88 棋盘的某个方格中#xff0c;马按走棋规则(马走日字)进行移动。每个方格只进入一次#xff0c;走遍棋盘上全部 64 个方格。
回溯问题模型
特征
解组织成树… 马踏棋盘c 题目回溯问题模型特征模型 代码 题目
马踏棋盘算法即骑士周游问题。将马放在国际象棋的 8×8 棋盘的某个方格中马按走棋规则(马走日字)进行移动。每个方格只进入一次走遍棋盘上全部 64 个方格。
回溯问题模型
特征
解组织成树的形式从根节点开始进行深度优先遍历访问节点时进行判断是否符合条件符合就继续否则进行回溯此节点后的都不用访问(与暴力算法的区别降低算法复杂度)
模型 代码
代码演示的是5*5的棋盘。递归的出口为步数k棋盘数M*M。递归主函数就是对每一坐标的8种走法进行判断。符合条件就调用递归函数。然后回溯上一步。map变量ma记录棋盘上的每一个坐标是否走过。没有走过的将其坐标加入map中成为键值记录第几步。
#includeiostream
#includemap
#includeiomanip //出输格式设定
using namespace std;
struct Pos{//定义坐标点int x;int y;Pos(int x,int y){this-xx;this-yy;}
};
int count0;//记录一共有多少种解法
void show(int M,mapPos,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.xb.x,a.yb.y);
}
//马走的步法是否有效如果出了格子表示bad即为true
bool outOfBounds(int M,Pos p){if(p.x0 || p.x M) return true;if(p.y0 || 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,mapPos,int ma,Pos p,int k){if(kM*M){count;cout countendl;show(M,ma);return true;} for(int i0;i8;i){Pos p1pdelta[i];if(outOfBounds(M,p1)) continue;if(ma.count(p1)) continue;ma[p1] k1;f(M,ma,p1,k1);ma.erase(p1);}return false;
}
void show(int M,mapPos,int ma){for(int i0;iM;i){for(int j0;jM;j){cout setw(3)ma[Pos(i,j)];}coutendl;}cout********************endl;
}
void horse(int M){mapPos,int ma;Pos p(0,0);ma[p]1;f(M,ma,p,1);
}
int main(){horse(5);cout总共有count种走法; return 0;
}
