[c++]代码库
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
#define INIT_SIZE 100 //存储空间初始分配量
#define SIZE_ADD 10 //存储空间分配增量
#define MAXLEN 10 //迷宫大小
struct Coord
{
int r;
int c;
bool operator == (const Coord &b) const
{
return (r==b.r && c==b.c);
}
};
struct Node
{
int ord;
Coord seat;
int di;
};
struct MazeType
{
int r;
int c;
char map[MAXLEN][MAXLEN];
};
int dir[][2]={1,0, -1,0, 0,1, 0,-1};
bool flag;
class Stack
{
public:
Stack ()
{
base = (Node *) malloc(INIT_SIZE * sizeof (Node));
if (!base) exit(0);
top = base;
size = INIT_SIZE;
}
bool empty () const { return top==base; }
void pop(Node &e);
void push(Node a);
private:
Node * top;
Node * base;
int size;
};
void Stack::push(Node item)
{
if (top - base >= size)
{
base = (Node *) realloc(base, (size+SIZE_ADD)*sizeof(Node));
if (!base) exit(0);
top = base + size;
size += SIZE_ADD;
}
*top++ = item;
}
void Stack::pop(Node &e)
{
if (top==base) return;
e = * -- top;
}
void MadeMap (MazeType &maze)
{
freopen ("test.in","r",stdin);
flag = false;
cin >> maze.r >> maze.c;
for(int i=0; i<maze.r; i++)
for(int j=0; j<maze.c; j++)
scanf (" %c",&maze.map[i][j]);
}
Coord NextPos(Coord &curpos, int i)
{
Coord ans;
ans = curpos;
ans.r += dir[i][0];
ans.c += dir[i][1];
return ans;
}
void MazePath(MazeType &maze, Coord start, Coord end)
{
Stack S;
Coord curpos; //当前坐标
Node e;
curpos=start;
int curstep=1;
do
{
if(maze.map[curpos.r][curpos.c]=='.') //此路可通
{
maze.map[curpos.r][curpos.c]='*';
e.ord=curstep;
e.seat=curpos;
e.di=1;
S.push(e);
if(curpos == end)
{
flag = true;
return;
}
curpos=NextPos(curpos,0);
curstep++;
}
else
{
if(!S.empty())
{
S.pop(e);
while(e.di==3 && !S.empty())
S.pop(e);
if(e.di < 4)
{
e.di++;
S.push(e);
curpos=NextPos(e.seat,e.di);
}
}
}
}while(!S.empty());
}
void PrintMaze(MazeType &maze)
{
if (flag)
{
cout << "迷宫路程图:\n";
for(int i=0;i<maze.r;i++)
{
cout << " ";
for(int j=0;j<maze.c;j++)
printf("%2c",maze.map[i][j]);
cout << endl;
}
}
else
cout << "\n***** 次迷宫无法从起点走到终点。 ******\n\n";
}
int main()
{
MazeType maze;
Coord start,end;
MadeMap (maze);
start.r = start.c = 0;
end.c = maze.c-1;
end.r = maze.r-1;
MazePath(maze, start, end);
PrintMaze(maze);
return 0;
}