先放代码,算法设计过程我随后再放上去
//author:1025679612@qq.com
//csdn:http://blog.csdn.net/wind_2008_06_29/article/details/7706531
#include <iostream> #include <list> using std::cout; using std::endl; using std::cin; using std::list; bool bVisitTag[387420489]= {false}; //9^9用来表示其中的一种状态是否被访问过 //========================================================================= //begin class Point define //========================================================================= class Point{ public: Point(); Point(const Point& rhs); public: bool operator==(const Point& rhs); bool operator!=(const Point& rhs); Point& operator= (const Point& rhs); public: int m_iRow; // int m_iCol; }; Point::Point(){} Point::Point(const Point& rhs){ m_iRow =rhs.m_iRow; m_iCol =rhs.m_iCol; } bool Point::operator!=(const Point& rhs){ return !operator==(rhs); } bool Point::operator==(const Point& rhs){ return (m_iRow== rhs.m_iRow)&&(m_iCol== rhs.m_iCol); } Point& Point::operator= (const Point& rhs){ m_iRow = rhs.m_iRow; m_iCol = rhs.m_iCol; return *this; } //========================================================================= //end of class Point define //========================================================================= //========================================================================= //begin class CState define //========================================================================= class CState{ //存储9宫的状态 public: CState(const CState& rhs); CState(); public: CState& operator=(const CState& rhs); bool operator==(const CState& rhs); public: int vValue[3][3]; Point m_Center; //我们设0的位置是Center }; CState::CState(const CState& rhs):m_Center(rhs.m_Center){ for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol) vValue[iRow][iCol] = rhs.vValue[iRow][iCol]; } } CState::CState(){} CState& CState::operator= (const CState& rhs){ m_Center = rhs.m_Center; for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol) vValue[iRow][iCol] = rhs.vValue[iRow][iCol]; } return *this; } bool CState::operator==(const CState& rhs){ if(m_Center != rhs.m_Center) return false; for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol) if(vValue[iRow][iCol] != rhs.vValue[iRow][iCol]) return false; } return true; } //========================================================================= //end of class CState define //========================================================================= CState StateBegin, StateEnd; //开始和结束状态 int Search(); int StateToInt(const CState& state);//编码 CState IntToState(int iState); //解码 int main(){ for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol){ cin>>StateBegin.vValue[iRow][iCol]; if(StateBegin.vValue[iRow][iCol]== 0){ StateBegin.m_Center.m_iRow= iRow; StateBegin.m_Center.m_iCol= iCol; } } } for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol){ cin>>StateEnd.vValue[iRow][iCol]; if(StateEnd.vValue[iRow][iCol]== 0){ StateEnd.m_Center.m_iRow= iRow; StateEnd.m_Center.m_iCol= iCol; } } } cout<<Search()<<endl; } int StateToInt(const CState& state){//编码 int iValue = 0; for(int iRow= 2; iRow>= 0; --iRow){ for(int iCol=2; iCol>= 0; --iCol){ iValue*= 9; iValue+= state.vValue[iRow][iCol]; } } return iValue; } CState IntToState(int iState){ //解码 CState state; for(int iRow= 0; iRow< 3; ++iRow){ for(int iCol= 0; iCol< 3; ++iCol){ state.vValue[iRow][iCol] = iState%9; iState/= 9; if(state.vValue[iRow][iCol]== 0){ state.m_Center.m_iRow = iRow; state.m_Center.m_iCol = iCol; } } } return state; } //========================================================================= //BFS search //========================================================================= int Search(){ list<CState> buffer1, buffer2; int iStep= 0; list<CState> *lpListUsed; //存放当前这一步 list<CState> *lpListNextStep; //存放下一步 if(StateBegin== StateEnd) return 0; //直接到达的话就是0了 lpListUsed = &buffer1; lpListNextStep = &buffer2; lpListUsed->push_back(StateBegin); int iPosition = StateToInt(StateBegin); bVisitTag[iPosition] = true; //bVisitTag[StateToInt(StateBegin)]= true; //打标记 while(!lpListUsed->empty()){ CState StateNow; CState StateNext; ++iStep; while(!lpListUsed->empty()){ StateNow= lpListUsed->front(); lpListUsed->pop_front(); if(StateNow== StateEnd){ return iStep-1; } if(StateNow.m_Center.m_iRow-1>= 0){ StateNext = StateNow; --StateNext.m_Center.m_iRow; StateNext.vValue[StateNow.m_Center.m_iRow][StateNow.m_Center.m_iCol] =StateNow.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol]; StateNext.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol] = 0; int iPosition = StateToInt(StateNext); if(!bVisitTag[iPosition]){ bVisitTag[iPosition]= true; lpListNextStep->push_back(StateNext); } } if(StateNow.m_Center.m_iRow+1< 3){ StateNext = StateNow; ++StateNext.m_Center.m_iRow; StateNext.vValue[StateNow.m_Center.m_iRow][StateNow.m_Center.m_iCol] =StateNow.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol]; StateNext.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol] = 0; int iPosition = StateToInt(StateNext); if(!bVisitTag[iPosition]){ bVisitTag[iPosition]= true; lpListNextStep->push_back(StateNext); } } if(StateNow.m_Center.m_iCol-1>= 0){ StateNext = StateNow; --StateNext.m_Center.m_iCol; StateNext.vValue[StateNow.m_Center.m_iRow][StateNow.m_Center.m_iCol] =StateNow.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol]; StateNext.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol] = 0; int iPosition = StateToInt(StateNext); if(!bVisitTag[iPosition]){ bVisitTag[iPosition]= true; lpListNextStep->push_back(StateNext); } } if(StateNow.m_Center.m_iCol+1< 3){ StateNext = StateNow; ++StateNext.m_Center.m_iCol; StateNext.vValue[StateNow.m_Center.m_iRow][StateNow.m_Center.m_iCol] =StateNow.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol]; StateNext.vValue[StateNext.m_Center.m_iRow][StateNext.m_Center.m_iCol] = 0; int iPosition = StateToInt(StateNext); if(!bVisitTag[iPosition]){ bVisitTag[iPosition]= true; lpListNextStep->push_back(StateNext); } } } std::swap(lpListUsed, lpListNextStep); } return -1; }