重排九宫格代码C++

// // main.cpp // chongpai9_ai // // Created by 孙文睿 on 2018/11/12. // Copyright © 2018 孙文睿. All rights reserved. // /****************************************************************************** * 使用深度优先、广度优先和A*算法解决九宫问题 ******************************************************************************/ #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include"data.h" #include"queue.h" #include"stack.h" #include"link.h" #define DEEPSEARCH 1 #define WIDESEARCH 2 #define ASTART 3 #define SEARCHTYPE ASTART //定义使用广度优先 //#define SHOWPROCESS //定义是否显示中间搜索过程 class SearchTree{ private: /***********************定义open表的数据类型************************/ #if SEARCHTYPE==WIDESEARCH Queue open; #elif SEARCHTYPE==DEEPSEARCH Stack open; #else Link open; #endif Stack close; public: void init(); //初始化数据 void extend(); //扩展close表尾节点并添加进open表 void moveToClose(); //将open表的头节点移动到close表中 bool success(); //判断搜索是否成功 bool openEmpty(); //判断open表是否为空 void showAnswer(); //显示最终结果 }; void SearchTree::showAnswer(){ close.show(); } bool SearchTree::openEmpty(){ return open.empty(); } void SearchTree::extend(){ DATATYPE temp[LINE][ROW],buf[LINE][ROW]; Data *pid; int n,m; pid=close.getTop(*buf); //将close表的最后一项记录复制到buf中 for(n=0;n<LINE;n++) for(m=0;m<ROW;m++) if(buf[n][m]==0)//寻找buf中0所在的位置，0表示空格 goto L1; L1: memcpy(temp,buf,DATASIZE*sizeof(DATATYPE)); if(n!=0){ //空格上移 temp[n][m]=temp[n-1][m]; temp[n-1][m]=0; if(close.exist(*temp)==false) open.push(*temp,&pid); #ifdef SHOWPROCESS //宏定义，决定时候输出中间过程 std::cout<<"move below data to open table:"<<std::endl; showElement(*temp); getchar(); #endif } memcpy(temp,buf,DATASIZE*sizeof(DATATYPE)); if(n!=2){ //空格下移 temp[n][m]=temp[n+1][m]; temp[n+1][m]=0; if(close.exist(*temp)==false) open.push(*temp,&pid); #ifdef SHOWPROCESS std::cout<<"move below data to open table:"<<std::endl; showElement(*temp); getchar(); #endif } memcpy(temp,buf,DATASIZE*sizeof(DATATYPE)); if(m!=0){ //空格左移 temp[n][m]=temp[n][m-1]; temp[n][m-1]=0; if(close.exist(*temp)==false) open.push(*temp,&pid); #ifdef SHOWPROCESS std::cout<<"move below data to open table:"<<std::endl; showElement(*temp); getchar(); #endif } memcpy(temp,buf,DATASIZE*sizeof(DATATYPE)); if(m!=2){ //空格右移 temp[n][m]=temp[n][m+1]; temp[n][m+1]=0; if(close.exist(*temp)==false) open.push(*temp,&pid); #ifdef SHOWPROCESS std::cout<<"move below data to open table:"<<std::endl; showElement(*temp); getchar(); #endif } } void SearchTree::moveToClose(){ DATATYPE dt[DATASIZE]; Data *pid; open.pop(dt,&pid); close.push(dt,&pid); } bool SearchTree::success(){ DATATYPE dt[DATASIZE]; close.getTop(dt); return memcmp(dt,*sg,DATASIZE*sizeof(DATATYPE))? false:true; } void SearchTree::init(){ open.init(); close.init(); int i,j; char a; //初始节点s0 std::cout<<"请输入初始状态（0代表空格）："<<std::endl; for(i=0;i<3;i++) { for(j=0;j<3;j++) { std::cin>>a; if('0'<=a && a<='9') s0[i][j]=a-'0'; else s0[i][j]=0; } } //目标节点sg std::cout<<"请输入目标状态（0代表空格）："<<std::endl; for(i=0;i<3;i++) { for(j=0;j<3;j++) { std::cin>>a; if('0'<=a && a<='9') sg[i][j]=a-'0'; else sg[i][j]=0; } } std::cout<<"初始状态为:"; showElement(*s0); std::cout<<"目标状态为:"; showElement(*sg); // std::cout<<"any key to continue"<<std::endl; getchar(); open.push(*s0,NULL); #ifdef SHOWPROCESS std::cout<<"below data move to open table:"<<std::endl; showElement(*s0); #endif } int main(){ #if SEARCHTYPE==WIDESEARCH puts("wide search"); #elif SEARCHTYPE==DEEPSEARCH puts("deep search"); #else puts("astart search"); #endif SearchTree st; st.init(); while(1){ //open表为空，问题无解 if(st.openEmpty()==true){ std::cout<<"there is no answer for this question, open table is empty"<<std::endl; exit(0); } //将open表的表头移动到close表中 st.moveToClose(); //判断是否搜索成功 if(st.success()==true){ std::cout<<"get answer:"<<std::endl; st.showAnswer(); exit(0); } //扩展close表 st.extend(); } }