Baiduのプログラミングコンテストの9宫図コードと解析
まずコードを入れて、アルゴリズムの設計過程は後で載せます。
//author:[email protected]//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;
}