华容道（huarongdao）C++ BFS求解

用C++编了个解传统益智游戏华容道的程序，不到1s可给出横刀立马通关步骤。主要用到bfs加上记录已遇到的局面（包括其对称的局面）帮助剪枝。简单修改初始化可解其它初始排布下的华容道。

 上图即为横刀立马开局

#include 
using namespace std;const int M=5,N=4;
const int caocao_qzIdx=1;
const string NAME[10]={"张飞","曹操","马超","黄忠","关羽","赵云","兵","兵","兵","兵"};
string templateStrMap="";
inline int e(int i,int j)
{return i*N+j;
}
struct QZ{int m=1,n=1;int i=0,j=0;int type=1,id=0;string name;QZ(){}QZ(int _m,int _n,int _i,int _j,int _id=0){m=_m;n=_n;i=_i;j=_j;if(m==1){if(n==1)type=1;elsetype=3;}else{if(n==1)type=2;elsetype=4;}id=_id;name=NAME[id];}void set(int _m,int _n,int _i,int _j){m=_m;n=_n;i=_i;j=_j;if(m==1){if(n==1)type=1;elsetype=3;}else{if(n==1)type=2;elsetype=4;}}
};
struct Move{int qzIdx,dir;string lastStrMap;vector lastQZs;
};
map path;
void print(int Map[M][N])
{for(int i=0;i &QZs)
{for(int i=0;i{2,4,4,2},{2,4,4,2},{2,3,3,2},{2,1,1,2},{1,0,0,1}};//0为空，1为1*1的兵，2为2*1的武将，3为1*2的武将，4为2*2的曹操string strMap="2442;2442;2332;2112;1001";vector QZs;int d=0;MAP(){QZs.push_back(QZ(2,1,0,0,0));QZs.push_back(QZ(2,2,0,1,1));QZs.push_back(QZ(2,1,0,3,2));QZs.push_back(QZ(2,1,2,0,3));QZs.push_back(QZ(1,2,2,1,4));QZs.push_back(QZ(2,1,2,3,5));QZs.push_back(QZ(1,1,3,1,6));QZs.push_back(QZ(1,1,3,2,7));QZs.push_back(QZ(1,1,4,0,8));QZs.push_back(QZ(1,1,4,3,9));}MAP(string &s,vector &_QZs,int _d=0){strMap=s;QZs=_QZs;d=_d; }void testQZs(){int map1[M][N]={0};for(int i=0;i0&&strMap[e(i,j-1)]==0){if(temp.m==1||strMap[e(i+1,j-1)]==0)return true;}}else if(dir==1){if(i>0&&strMap[e(i-1,j)]==0){if(temp.n==1||strMap[e(i-1,j+1)]==0)return true;}}else if(dir==2){if(m==1){if(n==1){if(j+1 &QZs)
{string s=templateStrMap;for(int I=0;I &resPath)
{ofstream wr;wr.open("hrd_out.txt",ios::app);for(int i=resPath.size()-1;i>=0;i--){Move &m=resPath[i];for(int i=0;i q;q.push(mymap);unordered_set visited;visited.insert(mymap.strMap);int D=0;while(!q.empty()){MAP tmpNode=q.front();string &s0=tmpNode.strMap;//print(s0);vector &QZs=tmpNode.QZs;//print(QZs);int d=tmpNode.d;q.pop();if(d>D){D=d;cout<{2,4,4,2},{2,4,4,2},{2,3,3,2},{2,1,1,2},{1,0,0,1}};for(int i=0;i resPath;while(path.count(s)){resPath.push_back(path[s]);s=path[s].lastStrMap;} for(int i=resPath.size()-1;i>=0;i--){cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！