前些日子，帮一个朋友做了个作业，是关于迷宫求解的演示
迷宫求解是个很经典的问题，这个我想不是讨论的问题
我想让大家看看我的思路，提提意见
下面是程序
//头文件
#ifndef Labyrinth_StructH
#define Labyrinth_StructH
#include <vcl.h>
#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;//一个优先方向另加四个方向
};
template<class T>class 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<LabyrinthRow*LabyrinthCol;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 <stdio.h>
#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<LabyrinthRow*LabyrinthCol;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<LabyrinthRow;k++)
for(int l=0;l<LabyrinthCol;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<LabyrinthRow*LabyrinthCol;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<LabyrinthRow*LabyrinthCol;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<LabyrinthRow*LabyrinthCol;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<LabyrinthRow;l++)
for(int k=0;k<LabyrinthCol;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;
CShed<SPoint>tShed;
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()<<mbOK, 0);
ChangeState(STATE_PASSED,STATE_PASS);
Refresh();
if(FMyEvent)
FMyEvent(EVENT_OK);
return;
}
break;
}
}while(CurrentSPoint);
if(CurrentSPoint==NULL)//没有解
{
MessageDlg("本迷宫没有通路。", mtWarning, TMsgDlgButtons()<<mbOK, 0);
if(FMyEvent)
FMyEvent(EVENT_OK);
return;
}
}
PowerExit=false;
}
//下面是栈的成员函数
template<class T>
__fastcall CShed<T>::CShed()
{
List=new TList();
}
template<class T> __fastcall CShed<T>::~CShed()
{
while(List->Count)
{
T *temp=(T *)List->Items[0];
delete temp;
List->Delete(0);
}
}
template<class T> T *CShed<T>::Pop()
{
if(!List->Count)
return NULL;
T *temp=(SPoint *)List->Items[List->Count-1];
List->Delete(List->Count-1);
return temp;
}
template<class T> void CShed<T>::Push(T *point)
{
List->Add(point);
}
///////////////////
