数据布局之栈的应用----迷宫
添加时间:2013-6-11 点击量:
这个用到了一些C++的常识了，因为须要用到动态建树数组和类的一些常识。
以前碰到类似的题目就很头疼，并且也不肯意去写，可是如今感觉只要肯花时候，
写起来并不那么艰苦，固然一次性完美的写出来，不失足不成能，然则在调试错误的过程中同样能感触感染到康乐。
推敲到节俭时候，我就随机生成了一个地图，矩阵的大小可以输入。1为可走，0为走不通。
代码并没有完美到我想要的目标，例如今朝只能寻找一条路线，多条路线还没有思路。
代码的首要思惟就是压栈和出栈
/
> File Name: maze.cpp
> Author: Darin
> Mail: dyy726＠qq.com
> Created Time: 2013年06月08日 礼拜四 06时36分24秒
/
＃include <iostream>
＃include <stdlib.h>
＃include <time.h>
using namespace std;
＃define orientationNum 4
int MazeMapLineNumber = 0;
typedef struct Position {
int xcoordinate;
int ycoordinate;
}POSITION;
typedef struct Node {
POSITION Pos;
struct Node pNext;
}NODE，PNode;
class CStack {
public:
PNode pTop;
PNode pBottom;
public:
CStack（）;
bool IsNull（）;
void Push（POSITION pos）;
void Pop（）;
POSITION GetTop（）;
void clear（）;
void ShowWay（）;
~CStack（）;
};
CStack::CStack（）{
pTop = pBottom = new NODE;
pTop->pNext = NULL;
}
bool CStack::IsNull（） {
if （pTop == pBottom）
return true;
return false;
}
void CStack::Push（POSITION pos） {
PNode p = new NODE;
p->Pos = pos;
p->pNext = pTop;
pTop= p;
}
void CStack::Pop（）{
if（!IsNull（）） {
PNode p = pTop;
pTop = p->pNext;
（p）;
} else cout<<The stack is null <<endl;
}
void CStack::ShowWay（） {
PNode p = pTop;
while（p->pNext != pBottom） {
cout<<（<<p->Pos.xcoordinate<<，<<p->Pos.ycoordinate<<） -> ;
p = p->pNext;
}
cout<<（<<p->Pos.xcoordinate<<，<<p->Pos.ycoordinate<<）;
}
POSITION CStack::GetTop（） {
return pTop->Pos;
}
void CStack::clear（） {
while（!IsNull（）） Pop（）;
}
CStack::~CStack（） {
clear（）;
}
bool isOutOfborder（POSITION pos） {
if（pos.ycoordinate<0 || pos.ycoordinate>=MazeMapLineNumber
||pos.xcoordinate<0 || pos.xcoordinate>=MazeMapLineNumber）
return true;
return false;
}
bool isequal（POSITION pos1，POSITION pos2） {
if（pos1.xcoordinate == pos2.xcoordinate &&
pos1.ycoordinate == pos2.ycoordinate） return true;
return false;
}
void PassMaze（int map，POSITION Inpos，POSITION OutPos） {
CStack MazeWay = new CStack（）;
POSITION CurPos = OutPos;
POSITION NewPos;
int i =0;
bool IsFind = false;
MazeWay->Push（CurPos）;
while（（!MazeWay->IsNull（））&&（!isequal（CurPos，Inpos））） {
//（!isOutOfborder（CurPos））
CurPos = MazeWay->GetTop（）;
IsFind = false;
for（i=0;i<orientationNum;i++） {
if（0 == i） {
//right
NewPos.xcoordinate = CurPos.xcoordinate;
NewPos.ycoordinate = CurPos.ycoordinate+1;
}
if（1 == i） {
//down
NewPos.xcoordinate = CurPos.xcoordinate+1;
NewPos.ycoordinate = CurPos.ycoordinate;
}
if（2 == i） {
//left
NewPos.xcoordinate = CurPos.xcoordinate;
NewPos.ycoordinate = CurPos.ycoordinate-1;
}
if（3 == i） {
//up
NewPos.xcoordinate = CurPos.xcoordinate-1;
NewPos.ycoordinate = CurPos.ycoordinate;
}
if（!isOutOfborder（NewPos） && map[NewPos.xcoordinate][NewPos.ycoordinate]） {
IsFind = true;
CurPos = NewPos;
map[NewPos.xcoordinate][NewPos.ycoordinate] = 0;
break;
}
}
if（IsFind） {
MazeWay->Push（CurPos）;
} else MazeWay->Pop（）;
}
if（MazeWay->IsNull（）） {
cout<<There is no way to go out of the maze<<endl;
} else MazeWay->ShowWay（）;
}
int main（） {
int i=0，j=0;
srand（（unsigned）time（NULL））;
cout<<Please input the row of the maze map:;
cin>>MazeMapLineNumber;
POSITION inpos;
POSITION outpos;
int pMap = new int [MazeMapLineNumber];
for （i=0;i<MazeMapLineNumber;i++） {
pMap[i] = new int [MazeMapLineNumber];
}
for （i=0;i<MazeMapLineNumber;i++） {
for （j=0;j<MazeMapLineNumber;j++） {
pMap[i][j] = rand（）％2;
cout<<pMap[i][j]<< ;
}
cout<<\n;
}
// for （i=0;i<MazeMapLineNumber;i++） {
// for （j=0;j<MazeMapLineNumber;j++） {
// cout<<pMap[i][j]<< ;
// }
// cout<<\n;
// }
cout<<Please input inpos.x :;
cin>>inpos.xcoordinate;
cout<<Please input inpos.y :;
cin>>inpos.ycoordinate;
cout<<Please input outpos.x :;
cin>>outpos.xcoordinate;
cout<<Please input outpos.y :;
cin>>outpos.ycoordinate;
PassMaze（pMap，inpos，outpos）;
return 0;
}
无论对感情还是对生活，“只要甜不要苦”都是任性而孩子气的，因为我们也不完美，我们也会伤害人。正因为我们都不完美，也因为生活从不是事事如意，所以对这些“瑕疵”的收纳才让我们对生活、对他人的爱变得日益真实而具体。—— 汪冰《世界再亏欠你，也要敢于拥抱幸福》
这个用到了一些C++的常识了，因为须要用到动态建树数组和类的一些常识。
以前碰到类似的题目就很头疼，并且也不肯意去写，可是如今感觉只要肯花时候，
写起来并不那么艰苦，固然一次性完美的写出来，不失足不成能，然则在调试错误的过程中同样能感触感染到康乐。
推敲到节俭时候，我就随机生成了一个地图，矩阵的大小可以输入。1为可走，0为走不通。
代码并没有完美到我想要的目标，例如今朝只能寻找一条路线，多条路线还没有思路。
代码的首要思惟就是压栈和出栈
/
> File Name: maze.cpp
> Author: Darin
> Mail: dyy726＠qq.com
> Created Time: 2013年06月08日 礼拜四 06时36分24秒
/
＃include <iostream>
＃include <stdlib.h>
＃include <time.h>
using namespace std;
＃define orientationNum 4
int MazeMapLineNumber = 0;
typedef struct Position {
int xcoordinate;
int ycoordinate;
}POSITION;
typedef struct Node {
POSITION Pos;
struct Node pNext;
}NODE，PNode;
class CStack {
public:
PNode pTop;
PNode pBottom;
public:
CStack（）;
bool IsNull（）;
void Push（POSITION pos）;
void Pop（）;
POSITION GetTop（）;
void clear（）;
void ShowWay（）;
~CStack（）;
};
CStack::CStack（）{
pTop = pBottom = new NODE;
pTop->pNext = NULL;
}
bool CStack::IsNull（） {
if （pTop == pBottom）
return true;
return false;
}
void CStack::Push（POSITION pos） {
PNode p = new NODE;
p->Pos = pos;
p->pNext = pTop;
pTop= p;
}
void CStack::Pop（）{
if（!IsNull（）） {
PNode p = pTop;
pTop = p->pNext;
（p）;
} else cout<<The stack is null <<endl;
}
void CStack::ShowWay（） {
PNode p = pTop;
while（p->pNext != pBottom） {
cout<<（<<p->Pos.xcoordinate<<，<<p->Pos.ycoordinate<<） -> ;
p = p->pNext;
}
cout<<（<<p->Pos.xcoordinate<<，<<p->Pos.ycoordinate<<）;
}
POSITION CStack::GetTop（） {
return pTop->Pos;
}
void CStack::clear（） {
while（!IsNull（）） Pop（）;
}
CStack::~CStack（） {
clear（）;
}
bool isOutOfborder（POSITION pos） {
if（pos.ycoordinate<0 || pos.ycoordinate>=MazeMapLineNumber
||pos.xcoordinate<0 || pos.xcoordinate>=MazeMapLineNumber）
return true;
return false;
}
bool isequal（POSITION pos1，POSITION pos2） {
if（pos1.xcoordinate == pos2.xcoordinate &&
pos1.ycoordinate == pos2.ycoordinate） return true;
return false;
}
void PassMaze（int map，POSITION Inpos，POSITION OutPos） {
CStack MazeWay = new CStack（）;
POSITION CurPos = OutPos;
POSITION NewPos;
int i =0;
bool IsFind = false;
MazeWay->Push（CurPos）;
while（（!MazeWay->IsNull（））&&（!isequal（CurPos，Inpos））） {
//（!isOutOfborder（CurPos））
CurPos = MazeWay->GetTop（）;
IsFind = false;
for（i=0;i<orientationNum;i++） {
if（0 == i） {
//right
NewPos.xcoordinate = CurPos.xcoordinate;
NewPos.ycoordinate = CurPos.ycoordinate+1;
}
if（1 == i） {
//down
NewPos.xcoordinate = CurPos.xcoordinate+1;
NewPos.ycoordinate = CurPos.ycoordinate;
}
if（2 == i） {
//left
NewPos.xcoordinate = CurPos.xcoordinate;
NewPos.ycoordinate = CurPos.ycoordinate-1;
}
if（3 == i） {
//up
NewPos.xcoordinate = CurPos.xcoordinate-1;
NewPos.ycoordinate = CurPos.ycoordinate;
}
if（!isOutOfborder（NewPos） && map[NewPos.xcoordinate][NewPos.ycoordinate]） {
IsFind = true;
CurPos = NewPos;
map[NewPos.xcoordinate][NewPos.ycoordinate] = 0;
break;
}
}
if（IsFind） {
MazeWay->Push（CurPos）;
} else MazeWay->Pop（）;
}
if（MazeWay->IsNull（）） {
cout<<There is no way to go out of the maze<<endl;
} else MazeWay->ShowWay（）;
}
int main（） {
int i=0，j=0;
srand（（unsigned）time（NULL））;
cout<<Please input the row of the maze map:;
cin>>MazeMapLineNumber;
POSITION inpos;
POSITION outpos;
int pMap = new int [MazeMapLineNumber];
for （i=0;i<MazeMapLineNumber;i++） {
pMap[i] = new int [MazeMapLineNumber];
}
for （i=0;i<MazeMapLineNumber;i++） {
for （j=0;j<MazeMapLineNumber;j++） {
pMap[i][j] = rand（）％2;
cout<<pMap[i][j]<< ;
}
cout<<\n;
}
// for （i=0;i<MazeMapLineNumber;i++） {
// for （j=0;j<MazeMapLineNumber;j++） {
// cout<<pMap[i][j]<< ;
// }
// cout<<\n;
// }
cout<<Please input inpos.x :;
cin>>inpos.xcoordinate;
cout<<Please input inpos.y :;
cin>>inpos.ycoordinate;
cout<<Please input outpos.x :;
cin>>outpos.xcoordinate;
cout<<Please input outpos.y :;
cin>>outpos.ycoordinate;
PassMaze（pMap，inpos，outpos）;
return 0;
}
无论对感情还是对生活，“只要甜不要苦”都是任性而孩子气的，因为我们也不完美，我们也会伤害人。正因为我们都不完美，也因为生活从不是事事如意，所以对这些“瑕疵”的收纳才让我们对生活、对他人的爱变得日益真实而具体。—— 汪冰《世界再亏欠你，也要敢于拥抱幸福》
