跪求高手 数据结构迷宫问题
发布网友
发布时间:2022-05-22 04:25
我来回答
共2个回答
热心网友
时间:2024-03-06 11:05
#define N 7 /*地图的第一维长度*/
#include <iostream.h>
#include <stdlib.h>
#include"ds.h"
#define O 5
#define P 5
typedef struct
{
int x;/* 行下标 */
int y;/* 列下标 */
int d;/* 运动方向 */
} DataType;
struct StackNode /* 链栈类型定义 */
{
struct StackNode *next;
DataType s;
};
typedef struct StackNode *LinkStack; /* 链栈类型的指针类型 */
int createEmptyStack_seq(LinkStack &S)
{
S=NULL;
return OK;
}
int isEmptyStack_seq( LinkStack pastack )
{
if(pastack==NULL)
return TRUE;
else return FALSE;
}
/* 在栈顶压入一元素x */
void push_seq( LinkStack &pastack, DataType x )
{
LinkStack p;
p = (LinkStack)malloc(sizeof(struct StackNode));
p->s=x;
p->next=pastack;
pastack=p;
}
/* 删除栈顶元素 */
void pop_seq( LinkStack &pastack )
{
LinkStack p;
if (!isEmptyStack_seq(pastack) )
{
p=pastack;
pastack=pastack->next;
free(p);
}
else
{
cout<<"栈已空,没有元素出栈!\n";
}
}
/* 当pastack所指的栈不为空栈时,求栈顶元素的值 */
DataType top_seq( LinkStack pastack )
{
if (!isEmptyStack_seq(pastack) )
return (pastack->s);
}
void pushtostack(LinkStack &st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}
void printpath(LinkStack st)
{
DataType element;
LinkStack S;
createEmptyStack_seq(S );
cout<<"The revers path is:\n"; /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st))
{
element = top_seq(st);
pop_seq(st);
push_seq(S,element);
}
while(!isEmptyStack_seq(S))
{
element = top_seq(S);
pop_seq(S);
cout<<"("<<element.x<<","<<element.y<<","<<element.d+1<<")"<<endl;
}
}
/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2)
{
int i, j, k, g, h;
LinkStack st;
DataType element;
createEmptyStack_seq(st );
maze[x1][y1] = 2; /* 从入口开始进入,作标记 */
pushtostack(st, x1, y1, -1); /* 入口点进栈 */
while ( !isEmptyStack_seq(st)) /* 走不通时,一步步回退 */
{
element = top_seq(st);
pop_seq(st);
i = element.x; j = element.y;
for (k = element.d + 1; k <= 3; k++) /* 依次试探每个方向 */
{
g = i + direction[k][0];h = j + direction[k][1];
if (g == x2 && h == y2 && maze[g][h] == 0) /* 走到出口点 */
{
pushtostack(st, i, j, k);
printpath(st); /* 打印路径 */
return;
}
if (maze[g][h] == 0) /* 走到没走过的点 */
{
maze[g][h] = 2; /* 作标记 */
pushtostack(st, i, j, k); /* 进栈 */
i = g; j = h; k = -1; /* 下一点转换成当前点 */
}
}
}
cout<<"The path has not been found.\n";/* 栈退完未找到路径 */
}
int main()
{
int direction[][2]={0,1,1,0,0,-1,-1,0};
int i,j;
int a[O][P],maze[O+2][P+2];
cout<<"请用0,1来设置"<<O<<"*"<<P<<"阶的矩阵迷宫"<<endl;
for(i=0;i<O;i++)
{
for(j=0;j<P;j++)
cin>>a[i][j];
}
for(i=1;i<=O;i++)
for(j=1;j<=P;j++)
maze[i][j]=a[i-1][j-1];
for(j=0;j<P+2;j++)
maze[0][j]=maze[O+1][j]=1;
for(i=0;i<O+2;i++)
maze[i][0]=maze[i][P+1]=1;
mazePath(maze,direction,1,1,O,P);
return 0;
}
这是我做的,完全符合要求,迷宫大小可以宏定义的时候设定,“ds.h”文件自己加一下就好了啊!
热心网友
时间:2024-03-06 11:06
#include<iostream>
using namespace std;
const int MAP_SIZE = 100;
template<typename Comparable>
class Stack
{
public:
Stack() { sPtr = NULL; }
bool isEmpty() { return sPtr == NULL; }
void push( const Comparable &x ){ sPtr = new Node( x, sPtr ); }
bool pop( Comparable &x )
{
if ( sPtr == NULL )
return false;
x = sPtr->data;
Node *tmp = sPtr;
sPtr = sPtr->next;
delete tmp;
return true;
}
~Stack()
{
Node *next = NULL;
for( Node *itr = sPtr; itr != NULL; itr = next )
{
next = itr->next;
delete itr;
}
}
private:
struct Node
{
Comparable data;
Node *next;
Node( const Comparable &d, Node *n = NULL )
: data( d ), next( n ) { }
};
Node *sPtr;
};
enum Direction{ Right, Down, Left, Up, Begin };
struct Position
{
int x, y;
Direction d;
Position( int _x = 0, int _y = 0, Direction _d = Begin )
: x( _x ), y( _y ), d( _d ) { }
};
int map[ MAP_SIZE ][ MAP_SIZE ];
bool visited[ MAP_SIZE ][ MAP_SIZE ];
int mapHeight, mapWidth;
int move_x[] = { 0, 1, 0, -1 };
int move_y[] = { 1, 0, -1, 0 };
void readMap()
{
cout << "输入迷宫的高度和宽度" << endl;
cin >> mapHeight >> mapWidth;
cout << "输入地图" << endl;
int i, j;
for( i = 1; i <= mapHeight; i ++ )
for( j = 1; j <= mapWidth; j ++ )
cin >> map[ i ][ j ];
for( i = 1; i <= mapHeight; i ++ )
for( j = 1; j <= mapWidth; j ++ )
map[ i ][ j ] = false;
}
bool exitMaze( int bx, int by, int ex, int ey, int M, int N )
{
Position p( bx, by );
Position newPos;
Stack<Position> s;
s.push( p );
bool first = true;
while( !s.isEmpty() )
{
s.pop( p );
if ( first )
first = false;
else
cout << "," << p.d << ")" << endl;
cout << "(" << p.x << "," << p.y;
visited[ p.x ][ p.y ] = true;
if ( p.x == ex && p.y == ey )
{
cout << ")" << endl;
return true;
}
for( int i = 0; i < 4; i ++ )
{
newPos.x = p.x + move_x[ i ];
newPos.y = p.y + move_y[ i ];
newPos.d = (Direction)i;
if ( newPos.x >= 1 && newPos.x <= M
&& newPos.y >= 1 && newPos.y <= N
&& !visited[ newPos.x ][ newPos.y ]
&& map[ newPos.x ][ newPos.y ] == 0 )
s.push( newPos );
}
}
return false;
}
int main()
{
readMap();
int sx, sy, ex, ey;
cout << "请输入迷宫的起始坐标" << endl;
cin >> sx >> sy;
cout << "请输入迷宫的出口坐标" << endl;
cin >> ex >> ey;
if( exitMaze( sx, sy, ex, ey, mapHeight, mapWidth ) )
cout << "成功!" << endl;
else
cout << "失败!" << endl;
return 0;
}
/*
测试数据
9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
1 1
9 8
*/