[原创]迷宫问题 - C++ - 新微赢技术网

藤蘿下的陽光

电梯直达

1^#

发表于 2009-11-2 04:43:50 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

*/ --------------------------------------------------------------------------------------
*/ 出自：编程中国 http://www.bc-cn.net
*/ 作者：风动 E-mail：xidiankeda492@yahoo.com.cn QQ：３０５６８７９１０
*/ 时间： 2007-7-21 编程论坛首发
*/ 声明：尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------

#include "iostream"
#include "stdlib.h"
#define STACKZISE 100
#define MAZESIAZE 4
using namespace std;
typedef struct
{
int x;
int y;
}PosType; //定义位置
typedef struct
{
PosType seat;
int sept;
int dirction;
}ElemType; //定义方向位置和走的次数
typedef struct NodeType
{
ElemType data;
NodeType *next;
}NodeType, *LinkType; //定义链表
typedef struct
{
LinkType top;
int size;
}StackType;
typedef struct
{
int col;
int row;
char arr[ STACKZISE+2][ STACKZISE+2];
}MazeType;
void InitStack(StackType &stack)
{
stack.top = NULL;
stack.size = 0;
} // 初始化栈
//进栈
void Push(StackType &stack, ElemType e)
{
LinkType p;
p = (LinkType)malloc(sizeof(NodeType));
p->next = stack.top;
p->data = e;
stack.top = p;
stack.size++;
}
//出栈
void Pop(StackType &stack, ElemType &e)
{
LinkType p;
p = stack.top;
e = p->data;
stack.top = p->next;
free(p);
stack.size--;
}
//初始化迷宫
void InitMaze(MazeType &maze, int arr[MAZESIAZE][MAZESIAZE], int m, int n)
{
maze.col = m+1;
maze.row = n+1;
maze.arr[m+1][n+1] = arr[m][n];
}
//标记不同路径
MazeType Marked(MazeType &maze, PosType curpos)
{
maze.arr[curpos.y][curpos.x] = '@';
return maze;
}
//标记走过路径
MazeType PrintMaze(MazeType &maze, PosType curpos)
{
maze.arr[curpos.y][curpos.x] = '*';
return maze;
}
//判断路径是否可通
bool Pass(MazeType &maze, PosType curpos)
{
if(maze.arr[curpos.y][curpos.x]==1 ||
maze.arr[curpos.y][curpos.x]=='#' || maze.arr[curpos.y][curpos.x]=='@'
||maze.arr[curpos.y][curpos.x]=='*')
return false;
else
return true;
}
//判断是否结束查找
bool Same(PosType curpos,PosType end)
{
if(curpos.x == end.x && curpos.y == end.y)
return true;
else
return false;
}
//下一步的位置
PosType NextPos(PosType &curpos, int dirction)
{
switch (dirction)
{
case 1 : curpos.x++; break;
case 2 : curpos.y++; break;
case 3 : curpos.x--; break;
case 4 : curpos.y--; break;
}
return curpos;
}
//判断是否为空栈
bool StackEmpty(StackType stack)
{
if(stack.top == NULL)
return true;
else
return false;
}
//判断有无路径可通
bool MazePath(MazeType &maze, PosType start, PosType end)
{
int curstep = 1;
ElemType e;
StackType stack;
InitStack(stack);
PosType curpos;
curpos= start;
bool found = false;
do
{
if(Pass(maze,curpos)) // the path pass
{
PrintMaze(maze, curpos);
e.sept = curstep;
e.seat = curpos;
e.dirction = 1;
Push(stack, e);
if(Same(curpos, end))
{
found = true;
return found;
}//if
else
{
curpos = NextPos(curpos, 1);//探索下一步
curstep++;
}//else
}//if
else //the path don't pass
{
if(!StackEmpty(stack))
{
Pop(stack, e);
while(e.dirction == 4 && !StackEmpty(stack))
{
Marked(maze,e.seat);
Pop(stack, e);
curstep--;
}//while
if(e.dirction<4)
{
e.dirction++;
Push(stack, e);
curpos = NextPos(e.seat, e.dirction);
}//if
}//if
}//else
}while(!StackEmpty(stack) && !found);
return found;
}//MazePath
void OutPutMaze(MazeType maze)
{
for( maze.col=1; maze.col<=MAZESIAZE;maze.col++)
{
for( maze.row=1; maze.row<=MAZESIAZE; maze.row++)
cout<<maze.arr[maze.col][maze.row]<<" ";
cout<<'\n';
}
}
void main()
{
int s_col;
int s_row;
int m;
int n;
int arr[MAZESIAZE][MAZESIAZE];
MazeType maze;
PosType start;
PosType end;
cout<<"*******************************************************************************"<<endl;
cout<<"************"<<" 只能读入：0或1 0：表示可通 1：表示不通"<<"******************"<<endl;
cout<<"*************"<<" @:表示走过但不通 *:表示通过的路径 "<<"******************"<<endl;
cout<<"*************"<<" 迷宫规模由: MAZESIAZE 确定可任意改变 "<<"******************"<<endl;
cout<<"*************"<<" 设计迷宫小于定义规模可在多出部分加0或1 "<<"******************"<<endl;
cout<<"*******************************************************************************"<<endl;
for(maze.col=0; maze.col<MAZESIAZE+2;maze.col++)
for(maze.row=0; maze.row<MAZESIAZE+2;maze.row++)
maze.arr[maze.col][maze.row] = '#';
for(m=0; m<MAZESIAZE; m++)
{
for(n=0; n<MAZESIAZE; n++)
{
cout<<"读入迷宫数据："<<endl;
cin>>arr[m][n];
while(arr[m][n]!=1 && arr[m][n]!=0)
{
cout<<"数据不合法请重输："<<endl;
cin>>arr[m][n];
}//while
InitMaze(maze, arr,m,n);
}//for
}//for
cout<<"读入迷宫为："<<endl;
for(int i=0; i< MAZESIAZE;i++)
{
for(int j=0; j< MAZESIAZE;j++)
cout<<arr[i][j]<<" ";
cout<<'\n';
}
cout<<"读入迷宫起始位置：";
cin>>start.x>>start.y;
while(start.x<0 ||start.x>MAZESIAZE || start.y<0 ||start.y>MAZESIAZE)
{
cout<<"输入不合法请重输：";
cin>>start.x>>start.y;
}
cout<<"("<<start.x<<")"<<"("<<start.y<<")"<<endl;
cout<<"出口位置："<<endl;
cin>>end.x>>end.y;
while(end.x<0 || end.x>MAZESIAZE || end.y<0 || end.y>MAZESIAZE)
{
cout<<"输入不合法请重输：";
cin>>end.x>>end.y;
}
cout<<"("<<end.x<<")"<<"("<<end.y<<")"<<endl;
if(MazePath(maze, start,end))
OutPutMaze(maze);
else
cout<<"the mazepath isn't found"<<endl;
}

收藏0