ITPub博客

首页 > IT职业 > IT生活 > 迷宫求解的过程演示 (转)

迷宫求解的过程演示 (转)

原创 IT生活 作者:worldblog 时间:2007-12-12 14:22:25 0 删除 编辑
迷宫求解的过程演示 (转)[@more@]

前些日子,帮一个朋友做了个作业,是关于迷宫求解的演示

迷宫求解是个很经典的问题,这个我想不是讨论的问题

我想让大家看看我的思路,提提意见

下面是程序

//头文件

#ifndef Labyrinth_StructH
#define Labyrinth_StructH

#include
#pragma hdrstop
typedef void __fastcall (__closure *TMyEvent)(int ID);

const int EVENT_PAINT=0;
const int EVENT_BACKDATE=1;
const int EVENT_OK=3;

const int STATE_ERROR=-1;
const int STATE_PASS=0;//可以通过
const int STATE_PASSED=1; //标记已经通过
const int STATE_CANNOTPASS=2;//不能通过
const int STATE_ENTRY=3; //入口点
const int STATE_END=4; //出口点

class SPoint
{
public:

  __fastcall ~SPoint()
  {

  }
  __fastcall SPoint()
  {
  PriorityDirection=1;
  Count=-1;
  }
  __fastcall SPoint(TPoint tPoint)
  {
  PriorityDirection=1;
  Count=-1;
  X=tPoint.x;
  Y=tPoint.y;
  }
  __fastcall SPoint(int tX,int tY)
  {
  PriorityDirection=1;
  Count=-1;
  X=tX;
  Y=tY;
  }
 int operator==(const SPoint& source)
  {
  return(Source.X==X&&Source.Y==Y);
  }
 int operator!=(const SPoint& Source)
  {
  return(Source.X!=X||Source.Y!=Y);
  }

int X;
int Y;
int Count;
int PriorityDirection;//一个优先方向另加四个方向
};


templateclass CShed //栈
{
public:
  TList *List;
  __fastcall CShed();
  __fastcall ~CShed();
  T *Pop();
  void Push(T *point);

};

 

class CLabyrinth
  {
  TCanvas *LabyrinthCanvas;
  int ImageHeight;
  int ImageWidth;

  int LabyrinthHeight;
  int LabyrinthWidth;

  int LabyrinthCol;
  int LabyrinthRow;

  int UnitHeight;
  int UnitWidth;

  int LeftSpace;
  int TopSpace;

  TStringList *AlreadPaSSList;
  int *LabyrinthData;

  Graphics::TBitmap *Bitmap_STATE_PASS;
  Graphics::TBitmap *Bitmap_STATE_PASSED;
  Graphics::TBitmap *Bitmap_STATE_CANNOTPASS;
  Graphics::TBitmap *Bitmap_STATE_ENTRY;
  Graphics::TBitmap *Bitmap_STATE_END;
  void SetMemory();
  void SetRowCol(int tRow,int tCol);
  bool GetNewPoint(int Direction,int &tRow,int &tCol,int &tState);
  void SetState(int tRow,int tCol,int tState);
  public:
  __fastcall CLabyrinth(AnsiString FileName);
  __fastcall CLabyrinth(int tWidth,int tHeight,TCanvas *tCanvas=NULL);
  __fastcall ~CLabyrinth();
  void __fastcall Assin(const CLabyrinth& Source)
  {
  LabyrinthCol=Source.LabyrinthCol;
  LabyrinthRow=Source.LabyrinthRow;
  LabyrinthData=new int[LabyrinthRow*LabyrinthCol];
  for(int k=0;k  LabyrinthData[k]=Source.LabyrinthData[k];
  }

  public:
  void ChangRowCol(int tRow,int tCol);
  void GetRowCol(int &tRow,int &tCol);
  void Updata();

  void SetSize(int tWidth,int tHeight);
  void GetSize(int &tWidth,int &tHeight);
  void GetSpace(int &tLeftSpace,int &tTopSpace);
  void SetCanvas(TCanvas *tCanvas);
  void Refresh();//整个画板进行刷新
  void Refresh(TRect rect,int tState=-1);
  void Refresh(TPoint point,int tState=-1);
  void Refresh(int tRow,int tCol,int tState=-1);
  void SaveToFile(AnsiString tFileName="");
  bool LoadFromFile(AnsiString tFileName="");
  int ConvertRC(int tRow,int tCol);
  int GetState(int tRow,int tCol);
  int GetState(TPoint tPoint);
  void ChangeState(int OldState,int NewState,int Times=-1);
  void FindResult(TPoint *StartPoint=NULL);
  public:
  bool PowerExit;
  bool IsChange;
  AnsiString FileName;

  TMyEvent FMyEvent;

  };

 


#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////

//下面是实现部分

#include
#pragma hdrstop
#include "Labyrinth_Struct.h"


__fastcall CLabyrinth::CLabyrinth(AnsiString FileName)
{
 LoadFromFile(FileName);
}
void CLabyrinth::Updata()
{
 UnitHeight=ImageHeight/LabyrinthRow;
 UnitWidth=ImageWidth/LabyrinthCol;

 LabyrinthHeight=UnitHeight*LabyrinthRow;
 LabyrinthWidth=UnitWidth*LabyrinthCol;

 LeftSpace=(ImageWidth-LabyrinthWidth)/2;
 TopSpace=(ImageHeight-LabyrinthHeight)/2;

}

__fastcall CLabyrinth::CLabyrinth(int tWidth,int tHeight,TCanvas *tCanvas)
{
 LabyrinthData=NULL;
 PowerExit=false;
 AlreadPassList=new TStringList();
 Bitmap_STATE_PASS=new Graphics::TBitmap();
 Bitmap_STATE_PASSED=new Graphics::TBitmap();
 Bitmap_STATE_CANNOTPASS=new Graphics::TBitmap();
 Bitmap_STATE_ENTRY=new Graphics::TBitmap();
 Bitmap_STATE_END=new Graphics::TBitmap();
 Bitmap_STATE_PASS->LoadFromResourceName((int)HInstance, "PASSNUNLL");
 Bitmap_STATE_PASSED->LoadFromResourceName((int)HInstance, "PASS");
 Bitmap_STATE_CANNOTPASS->LoadFromResourceName((int)HInstance, "CANNOTPASS");
 Bitmap_STATE_ENTRY->LoadFromResourceName((int)HInstance, "STATE_ENTRY");
 Bitmap_STATE_END->LoadFromResourceName((int)HInstance, "STATE_END");
 IsChange=false;
 LabyrinthData=NULL;
 LabyrinthCol=40;
 LabyrinthRow=40;
 LabyrinthCanvas=tCanvas;
 ImageHeight=tHeight;
 ImageWidth=tWidth;
 SetRowCol(LabyrinthRow,LabyrinthCol);
}
__fastcall CLabyrinth::~CLabyrinth()
{
 delete Bitmap_STATE_PASS;
 delete Bitmap_STATE_PASSED;
 delete Bitmap_STATE_CANNOTPASS;
 delete Bitmap_STATE_ENTRY;
 delete Bitmap_STATE_END;

 if(LabyrinthData)
  {
  delete []LabyrinthData;
  LabyrinthData=NULL;
  }
}


void CLabyrinth::SetMemory()
{
 if(LabyrinthData)
  {
  delete []LabyrinthData;
  LabyrinthData=NULL;
  }

 LabyrinthData=new int[LabyrinthRow*LabyrinthCol];
 for(int k=1;k  LabyrinthData[k]=STATE_PASS;
 LabyrinthData[0]=STATE_ENTRY;
 LabyrinthData[LabyrinthRow*LabyrinthCol-1]=STATE_END;
}
void CLabyrinth::SetRowCol(int tRow,int tCol)
{
 LabyrinthCol=tCol;
 LabyrinthRow=tRow;
 Updata();
 SetMemory();
}
void CLabyrinth::SetCanvas(TCanvas *tCanvas)
{
 LabyrinthCanvas=tCanvas;
}
void CLabyrinth::Refresh()
{
 if(LabyrinthCanvas!=NULL)
  {
  LabyrinthCanvas->Brush->Color=clBlack;
  LabyrinthCanvas->FillRect(Rect(0,0,ImageWidth,ImageHeight));
  }
 for(int k=0;k  for(int l=0;l  Refresh(k+1,l+1);
}
void CLabyrinth::Refresh(TRect rect,int tState)
{
 int tLeft,tTop,tRight,tBottom;
 tLeft=rect.Left-LeftSpace;
 tTop=rect.Top-TopSpace;
 tBottom=rect.Bottom-TopSpace;
 tRight=rect.Right-LeftSpace;

 int tLeftCol=tLeft/UnitWidth+1;
 int tLeftRow=tTop/UnitHeight+1;
 int tRightCol=tRight/UnitWidth;
 int tRightRow=tBottom/UnitHeight;
 tRightCol+=tRight%UnitWidth>0?1:0;
 tRightRow+=tBottom%UnitHeight>0?1:0;
 for(int k=tLeftRow;k<=tRightRow;k++)
  for(int l=tLeftCol;l<=tRightCol;l++)
  Refresh(k,l,tState);

}
void CLabyrinth::Refresh(TPoint point,int tState)
{
  int tCol=(point.x-LeftSpace)/UnitWidth;
  int tRow=(point.y-TopSpace)/UnitHeight;
  tCol+=point.x%UnitWidth>0?1:0;
  tRow+=point.y%UnitHeight>0?1:0;
  Refresh(tRow,tCol,tState);

}
void CLabyrinth::Refresh(int tRow,int tCol,int tState)
{
 if(LabyrinthCanvas==NULL)
  return;
 if(tRow<0||tCol<0||tRow>LabyrinthRow||tCol>LabyrinthCol)
  return;
 int OldState=LabyrinthData[ConvertRC(tRow,tCol)];
 if(tState!=-1)
  {
  if(OldState==STATE_ENTRY||OldState==STATE_END)
  return;
  LabyrinthData[ConvertRC(tRow,tCol)]=tState;
  IsChange=true;
  }
  else
  tState=OldState;

 switch(tState)
 {
  case STATE_PASS: LabyrinthCanvas->StretchDraw(Rect(UnitWidth*(tCol-1)+LeftSpace,UnitHeight*(tRow-1)+TopSpace,UnitWidth*tCol+LeftSpace,UnitHeight*tRow+TopSpace),Bitmap_STATE_PASS);break;
  case STATE_PASSED:LabyrinthCanvas->StretchDraw(Rect(UnitWidth*(tCol-1)+LeftSpace,UnitHeight*(tRow-1)+TopSpace,UnitWidth*tCol+LeftSpace,UnitHeight*tRow+TopSpace),Bitmap_STATE_PASSED); break;
  case STATE_CANNOTPASS:LabyrinthCanvas->StretchDraw(Rect(UnitWidth*(tCol-1)+LeftSpace,UnitHeight*(tRow-1)+TopSpace,UnitWidth*tCol+LeftSpace,UnitHeight*tRow+TopSpace),Bitmap_STATE_CANNOTPASS); break;
  case STATE_ENTRY:LabyrinthCanvas->StretchDraw(Rect(UnitWidth*(tCol-1)+LeftSpace,UnitHeight*(tRow-1)+TopSpace,UnitWidth*tCol+LeftSpace,UnitHeight*tRow+TopSpace),Bitmap_STATE_ENTRY); break;
  case STATE_END:LabyrinthCanvas->StretchDraw(Rect(UnitWidth*(tCol-1)+LeftSpace,UnitHeight*(tRow-1)+TopSpace,UnitWidth*tCol+LeftSpace,UnitHeight*tRow+TopSpace),Bitmap_STATE_END); break;
  default: break;
 }


}
int CLabyrinth::ConvertRC(int tRow,int tCol)
{
 return((tRow-1)*LabyrinthCol+tCol-1);

}

void CLabyrinth::SetSize(int tWidth,int tHeight)
{
 LabyrinthHeight=tHeight;
 LabyrinthWidth=tWidth;
 UnitHeight=LabyrinthHeight/LabyrinthRow;
 UnitWidth=LabyrinthWidth/LabyrinthCol;
 LabyrinthHeight=UnitHeight*LabyrinthRow;
 LabyrinthWidth=UnitWidth*LabyrinthCol;
 Refresh();


}
void CLabyrinth::GetSpace(int &tLeftSpace,int &tTopSpace)
{
 tLeftSpace=LeftSpace;
 tTopSpace=TopSpace;

}

void CLabyrinth::GetSize(int &tWidth,int &tHeight)
{
 tHeight=LabyrinthHeight;
 tWidth=LabyrinthWidth;

}
int CLabyrinth::GetState(int tRow,int tCol)
{
 if(tRow>0&&tCol>00&&tRow<=LabyrinthRow&&tCol<=LabyrinthCol)
  return(LabyrinthData[ConvertRC(tRow,tCol)]);
  return STATE_ERROR;
}

int CLabyrinth::GetState(TPoint tPoint)
{
  int tCol=tPoint.x/UnitWidth;
  int tRow=tPoint.y/UnitHeight;
  tCol+=tPoint.x%UnitWidth>0?1:0;
  tRow+=tPoint.y%UnitHeight>0?1:0;
  if(tRow>0&&tCol>0&&tRow<=LabyrinthRow&&tCol<=LabyrinthCol)
  return(LabyrinthData[ConvertRC(tRow,tCol)]);
  return STATE_ERROR;

}
void CLabyrinth::SaveToFile(AnsiString tFileName)
{
  if(tFileName.IsEmpty())
  tFileName=FileName;
  if(tFileName.IsEmpty())
  return;
  FILE *in;
 try
 {
 try
 {
  if ((in = fopen(tFileName.c_str(), "w+"))== NULL)
  {
  ShowMessage("不能打开文件!!!");
  throw(0);
  }
  char SMark[5]="Labyr";
  int tEdition=100;
  fprintf(in, " %s ", SMark);
  fprintf(in, " %d ", tEdition);
  fprintf(in, " %d %d ", LabyrinthRow,LabyrinthCol);
  for(int k=0;k  fprintf(in, " %d ", LabyrinthData[k]);
  FileName=tFileName;
  IsChange=false;
 }
 __finally
 {
  fclose(in);
 }
 }
 catch(...)
 {
  return;
 }
}
void CLabyrinth::GetRowCol(int &tRow,int &tCol)
{
 tRow=LabyrinthRow;
 tCol=LabyrinthCol;
}
void CLabyrinth::ChangRowCol(int tRow,int tCol)
{
 if(tRow>60||tRow<10||tCol>60||tRow<10)
  {
  ShowMessage("列和行超出边界(60>x>10)");
  return;
  }
 LabyrinthData=NULL;
 LabyrinthCol=tCol;
 LabyrinthRow=tRow;
 SetRowCol(LabyrinthRow,LabyrinthCol);
 IsChange=true;
 Refresh();
}
void CLabyrinth::SetState(int tRow,int tCol,int tState)
{
  if(tRow>0&&tCol>0&&tRow<=LabyrinthRow&&tCol<=LabyrinthCol)
  {
  if(GetState(tRow,tCol)!=STATE_ENTRY&&GetState(tRow,tCol)!=STATE_END)
  LabyrinthData[ConvertRC(tRow,tCol)]=tState;
  }
}

void CLabyrinth::ChangeState(int OldState,int NewState,int Times)
{
 int tCount=0;
 for(int k=0;k  {
  if(LabyrinthData[k]==OldState)
  {
  IsChange=true;
  LabyrinthData[k]=NewState;
  tCount++;
  int tCol,tRow;
  tRow=k/LabyrinthCol;
  tCol=k%LabyrinthCol;
  Refresh(tRow+1,tCol+1);
  if(tCount==Times)
  return ;
  }
  }

}

bool CLabyrinth::LoadFromFile(AnsiString tFileName)
{
 FILE *in;
 try
  {
 try
 {
  if ((in = fopen(tFileName.c_str(), "r"))== NULL)
  {
  ShowMessage("不能打开文件!!!");
  throw(0);
  }
  rewind(in);
  char  Mark[5];
  AnsiString SMark="Labyr";
  fscanf(in, " %s ", Mark);
  AnsiString tempStr=Mark;
  tempStr=tempStr.SubString(1,5);
  if(tempStr!=SMark)
  {
  ShowMessage("该文件不是迷宫数据文件");
  throw(0);
  }
  int tRow,tCol;
  int tEdition;
  fscanf(in, " %d ", &tEdition);
  fscanf(in, " %d %d ", &tRow,&tCol);
  LabyrinthCol=tCol;
  LabyrinthRow=tRow;

  SetMemory();
  int tState;
  for(int k=0;k  {
  if(feof(in))
  {
  ShowMessage("文件被破坏!!!");
  throw(0);
  }
  fscanf(in, " %d ", &tState);
  LabyrinthData[k]=tState;
  }
  FileName=tFileName;
  IsChange=false;


 }
 __finally
 {
  fclose(in);
 }
  }
  catch(...)
  {
  return false;
  }
}


bool CLabyrinth::GetNewPoint(int Direction,int &tRow,int &tCol,int &tState)
{
int OldCol=tCol;
int OldRow=tRow;
switch(Direction)
 {
  case 1: tCol=tCol;tRow=tRow-1;break;
  case 2: tCol=tCol+1;tRow=tRow;break;
  case 3: tCol=tCol;tRow=tRow+1;break;
  case 4: tCol=tCol-1;tRow=tRow;break;
  default :return false;
 }
 tState=GetState(tRow+1,tCol+1);
 if((tState==STATE_PASS||tState==STATE_END)&&AlreadPassList->IndexOf(Format("X:%dY:%d",ARRAYOFCONST((OldCol+1,OldRow+1))))<0)//发现了新的结点
  return true;
 return false;
}
void CLabyrinth::FindResult(TPoint *tStartPoint)
{
  SPoint *StartSPoint;
  SPoint *CurrentSPoint;
  SPoint *StopSPoint;//=new SPoint();
  TPoint StartPoint;
  TPoint StopPoint;
  int tCount=0;
  AlreadPassList->Clear();
  for(int l=0;l  for(int k=0;k  {
  if(LabyrinthData[l*LabyrinthCol+k]==STATE_ENTRY)
  {
  StartPoint.x=k;
  StartPoint.y=l;
  tCount++;
  break;
  }
  if(LabyrinthData[l*LabyrinthCol+k]==STATE_END)
  {
  StopPoint.x=k;
  StopPoint.y=l;  tCount++;
  break;

  }
  if(tCount==2)
  break;
  }

  if(tStartPoint!=NULL)
  CurrentSPoint=new SPoint(*tStartPoint);
  else
  CurrentSPoint=new SPoint(StartPoint);
  StopSPoint=new SPoint(StopPoint);
  StartSPoint=CurrentSPoint;
  if(CurrentSPoint->X>StopSPoint->X)
  CurrentSPoint->PriorityDirection=4;
  else
  CurrentSPoint->PriorityDirection=2;

  CShedtShed;

  int NowState;
  int CX,CY;
  while(1)
  {
  if(PowerExit)
  break;
  do{
  if(PowerExit)
  break;
  CurrentSPoint->Count++;
  bool tNeedPush;
  CX=CurrentSPoint->X;
  CY=CurrentSPoint->Y;
  switch(CurrentSPoint->Count)
  {
  case 0: tNeedPush=GetNewPoint(CurrentSPoint->PriorityDirection,CY,CX,NowState); break;
  case 1:
  case 2:
  case 3:
  case 4: tNeedPush=GetNewPoint(CurrentSPoint->Count,CY,CX,NowState);break;
  default: tNeedPush=false;
  SetState(CurrentSPoint->Y+1,CurrentSPoint->X+1,STATE_PASS);
  Refresh(CurrentSPoint->Y+1,CurrentSPoint->X+1);
  AlreadPassList->Add(Format("X:%dY:%d",ARRAYOFCONST((CurrentSPoint->X+1,CurrentSPoint->Y+1))));
  CurrentSPoint=tShed.Pop();
  if(FMyEvent)
  FMyEvent(EVENT_BACKDATE);
  break;
  }
  if(tNeedPush)
  {
  int OldPriorityDirection=CurrentSPoint->PriorityDirection;
  int OldCount=CurrentSPoint->Count;
  SetState(CurrentSPoint->Y+1,CurrentSPoint->X+1,STATE_PASSED);
  Refresh(CurrentSPoint->Y+1,CurrentSPoint->X+1);
  tShed.Push(CurrentSPoint);
  if(FMyEvent)
  FMyEvent(EVENT_PAINT);
  CurrentSPoint=new SPoint(CX,CY);
  if(OldCount==0)
  CurrentSPoint->PriorityDirection=OldPriorityDirection;
  else
  CurrentSPoint->PriorityDirection=OldCount;
  if(NowState==STATE_END)
  {
  MessageDlg("恭喜你!!!", mtInformation, TMsgDlgButtons()<  ChangeState(STATE_PASSED,STATE_PASS);
  Refresh();
  if(FMyEvent)
  FMyEvent(EVENT_OK);
  return;
  }
  break;
  }
  }while(CurrentSPoint);
  if(CurrentSPoint==NULL)//没有解
  {
  MessageDlg("本迷宫没有通路。", mtWarning, TMsgDlgButtons()<  if(FMyEvent)
  FMyEvent(EVENT_OK);
  return;
  }
  }

  PowerExit=false;
}

//下面是栈的成员函数
template
__fastcall CShed::CShed()
{
 List=new TList();
}
template __fastcall CShed::~CShed()
{
 while(List->Count)
  {
  T *temp=(T *)List->Items[0];
  delete temp;
  List->Delete(0);
  }
}
template T *CShed::Pop()
{
 if(!List->Count)
  return NULL;

  T *temp=(SPoint *)List->Items[List->Count-1];
  List->Delete(List->Count-1);
  return temp;

 

}
template void  CShed::Push(T *point)
{
  List->Add(point);

}
///////////////////

 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752043/viewspace-992134/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    6241
  • 访问量
    2448001