aa.cpp

九宫问题的深度和广度优先算法

/******************************************************************************
 * 使用深度优先、广度优先和A*算法解决九宫问题
******************************************************************************/

#include<stdio.h>
#include<iostream.h>
#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 WIDESEARCH   //定义使用广度优先


//#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    //宏定义，决定时候输出中间过程
        cout<<"move below data to open table:"<<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
        cout<<"move below data to open table:"<<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
        cout<<"move below data to open table:"<<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
        cout<<"move below data to open table:"<<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();
    //初始节点S0
    s0[0][0]=2;s0[0][1]=8;s0[0][2]=3;
    s0[1][0]=1;s0[1][1]=0;s0[1][2]=4;
    s0[2][0]=7;s0[2][1]=6;s0[2][2]=5;
    //目标节点Sg
    sg[0][0]=1;sg[0][1]=2;sg[0][2]=3;
    sg[1][0]=8;sg[1][1]=0;sg[1][2]=4;
    sg[2][0]=7;sg[2][1]=6;sg[2][2]=5;
    //显示信息
    cout<<"s0:"<<endl;
    showElement(*s0);
    cout<<"sg:"<<endl;
    showElement(*sg);
    cout<<"any key to continue"<<endl;
    getchar();

    open.push(*s0,NULL);
#ifdef SHOWPROCESS    
    cout<<"below data move to open table:"<<endl;
    showElement(*s0);
#endif

}


void 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){    
            cout<<"there is no answer for this question, open table is empty"<<endl;
            exit(0);
        }
        //将open表的表头移动到close表中
        st.moveToClose();            
        //判断是否搜索成功
        if(st.success()==true){        
            cout<<"get answer:"<<endl;
            st.showAnswer();
            exit(0);
        }
        //扩展close表
        st.extend();                
    }
}