分类: C/C++
2010-06-08 09:40:48
在今天早上的时候,我还到处“求医问药”希望能解决程序中未能解决的问题,郁闷了一天,总算是明白问题是出在什么地方的了。好了,还是先将迷宫算法的解决 算法发上来,之后再讨论之前的问题出在什么地方,又是怎样解决的。
迷宫算法如下:
//#############################################################//
//在VC6及vs2005里面都没有调试通过,在MinGW Developer Studio和gCC里面调试通过
#include
#include
#include
#include
#define MAZE_ROW 9
#define MAZE_COL 7
char maze[MAZE_ROW][MAZE_COL]={
' ',' ',' ','#','#','#','#',
'#','#',' ','#','#','#','#',
' ','#',' ','#','#','#','#',
' ','#',' ',' ',' ',' ',' ',
' ',' ','#','#','#','#',' ',
'#',' ',' ',' ',' ','#',' ',
'#','#',' ','#',' ','#',' ',
' ',' ',' ',' ','#','#',' ',
' ',' ','#',' ',' ','#',' ',
};
typedef struct {
int gn;
int fn;
int flag; //1——in open; 2——in close
}GFN;
map
int Bi=0, Bj=0;
int Ei=6, Ej=6;
bool opensort(int n1,int n2)
{
map
pos1 = gmap.find(n1);
pos2 = gmap.find(n2);
return pos1->second->fn < pos2->second->fn;
}
void getway(int i,int j,int gn); //输出路径
void printmaze();
void printway();
bool isok(int i,int j);//判断n1位置为迷宫中可以走的位置
int main()
{
vector
vector
map
vector
int n,gn,fn;
int n1,gn1,fn1;
int ci,cj;
int ni,nj;
GFN* pgf = NULL;
printmaze();
ci = Bi;
cj = Bj;
n = ci*MAZE_COL + cj;
gn = 0;
fn = abs(Ei-ci)+abs(Ej-cj);
pgf=new GFN;
pgf->gn = 0;
pgf->fn = fn;
pgf->flag = 1;
gmap[n] = pgf;
open.push_back(n);
while(!open.empty()){
n = open.front(); //pop front from open
open.erase(open.begin());
ci = n/MAZE_COL; //the corren sit
cj = n%MAZE_COL;
pos = gmap.find(n); //find the sit
gn = pos->second->gn;
fn = pos->second->fn;
pos->second->flag = 2;
close.push_back(n); //push n into close
if(ci==Ei && cj==Ej)
{
cout<<"找到最短路径,长度为:"<
// printway();
return 1;
}
gn1 = gn+1;
for(int d=0; d<4; ++d){
ni = ci;
nj = cj;
switch(d){
case 0 : //left derect
nj = cj-1;
break;
case 1 : //up derect
ni = ci-1;
break;
case 2 : //right derect
nj = cj+1;
break;
case 3 : //down derect
ni = ci+1;
break;
}//end_switch
if(isok(ni,nj)){
n1 = ni*MAZE_COL+nj;
fn1 = abs(Ei-ni)+abs(Ej-nj)+gn1;
pos = gmap.find(n1);
if(pos!=gmap.end()){//n1 is old
if(pos->second->fn > fn1){
pos->second->fn = fn1;
pos->second->gn = gn1;
if(pos->second->flag==2){
it = find(close.begin(),close.end(),n1);
close.erase(it);
open.push_back(n1);
}
sort(open.begin(),open.end(),opensort );
}
}
else{//
pgf = new GFN;
pgf->gn = gn1;
pgf->fn = fn1;
pgf->flag = 1;
gmap[n1] = pgf;
open.push_back(n1);
sort(open.begin(),open.end(),opensort );
}//end_else
}//end_if
}//end_for
}//end_while
cout<<"没有路径可以到达出口!\n\n\n"<
}
bool isok(int i,int j) //判断n1位置为迷宫中可以走的位置
{
if( i>=0 && i<=MAZE_ROW && j>=0 &&
j<=MAZE_COL && maze[i][j]==' ')
return true;
return false;
}
void printmaze() } 早上的问题: 原来在这个程序里面,我用的是list作为open和close的容器,然而在使用
办法一:将list改为vector容器,相应的open.pop_front()改为open.erase(pop.begin());这
样 //#############################################################// 在这里谢谢一个朋友给的一个答复,他解释如下(其实不是这里的问题,但是他的答复让我知道了这个方法): Map是一个通过key(键)来获得value(值)的模板类。另一个问题是你希望在map中使用自己的类而不是已有的数据类型,比如现在已经用过
的int。建立一个“为模板准备的(template-ready)”类,你必须确保在该类中包含一些成员函数和重载操作符。下面的一些成员是必须的: class CStudent int main(int argc, char* argv[]) /****************************************************************/
{
cout<<"迷宫:"<
cout<<"入口坐标为:("<
//#############################################################//
办法二:对open排序的地方(及sort(open.bengin(),open.end().opensort()))改为
open.sort(opensort() )不过这时opensort要改为如下结构:
struct opensort: public binary_function
{
bool operator () (const int& n1,const int& n2)const
{
map
pos1 = gmap.find(n1);
pos2 = gmap.find(n2);
return pos1->second->fn <
pos2->second->fn;
}
};
这样,就没有问题了,哈哈,太好了,遇到问题,郁闷了一天,现在总算明白了
•缺省的构造函数(通常为空)
•拷贝构造函数
•重载的”=”运算符
你应该重载尽可能多的运算符来满足特定模板的需要,比如,如果你想定义一个类作为
map中的键(key),你必须重载相关的运算符。但在这里不对重载运算符做过多讨论了。
//程序:映射自定义的类。
//目的:说明在map中怎样使用自定义的类。
#include
#include
#include
#include
{
public:
int nStudentID;
int nAge;
public:
CStudent(){}//缺省构造函数——通常为空
//完整的构造函数
CStudent(int nSID, int nA){ nStudentID=nSID; nAge=nA;}
//拷贝构造函数
CStudent(const CStudent& ob){ nStudentID=ob.nStudentID;
nAge=ob.nAge;}
// 重载“=”
void operator = (const CStudent& ob){nStudentID=ob.nStudentID;
nAge=ob.nAge;}
};
{
map
mapStudent["Joe Lennon"] = CStudent(103547, 22);
mapStudent["Phil McCartney"] = CStudent(100723, 22);
mapStudent["Raoul Starr"] = CStudent(107350, 24);
mapStudent["Gordon Hamilton"] = CStudent(102330, 22);
// 通过姓名来访问Cstudent类中的成员
cout <<"The Student number for Joe Lennon is "<<
(mapStudent["Joe Lennon"].nStudentID) << endl;
return 0;
}
谢谢这位朋友,来自: