先放代码,算法设计过程我随后再放上去
//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;
}
分享到:
相关推荐
百度之星-编程大赛初赛练习题 题目描述: 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
华为编程大赛的一些规范华为编程大赛的一些规范华为编程大赛的一些规范华为编程大赛的一些规范华为编程大赛的一些规范
做贡献,不要分了 做贡献,不要分了 做贡献,不要分了
是《嵌入式系统编程源代码解析》书的配套光盘,含源代码。
Google编程大赛题目Google编程大赛题目Google编程大赛题目
C语言高级编程及实例解析源代码压缩包包括: C语言高级编程及实例解析 C语言高级编程及实例解析源代码
作品就叫OMNISCENT 这个程序是97年Mekka ’97 4K Intro比赛的一等奖作品,汇编语言所写。整个程序全长4095字节, 生成.com程序只有4K,可是却实现了3D动画的效果,还有一段背景音乐,画面是游戏天旋地转的一个场景
世界编程大赛头名程序
2021年4月最新结束的世界编程大赛的作品,解压后可以直接运行查看效果.排名前5作品, 第三名的是一个webGL作品
近20年所有获奖代码,很好也很奇葩 https://submit.ioccc.org/ The 21st International Obfuscated C Code Contest The 21st International Obfuscated C Code Contest is open from 2012-Aug-15 03:14:15 UTC to ...
用于UR机器人的通信及通信数据解析,内容包括完整的Windows Sockets编程,以及UR机器人的通信协议解析、字节顺序变换等。
编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计大赛.doc编程设计...
世界编程大赛作品,世界编程大赛作品,世界编程大赛作品
内附2013年华为编程大赛题目~
世界编程大赛前三名作品非常精彩大家可以下载看看。
华为 编程 大赛 试题 比赛 华为 编程 大赛 试题 比赛
世界编程大赛第一名的作品及解读 很有趣的
内含5个排名前五的作品,每个尺寸仅有64KB。解压后可以直接运行查看效果.与之前年份的大神作品质量相当
百度之星程序设计大赛,百度之星大赛每年赛题集锦全集,百度之星大赛每年赛题集锦全集