问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

跪求高手 数据结构迷宫问题

发布网友 发布时间: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
*/
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
...换手机号显示你以设置拒收微信登陆.换绑.注册短信怎么解决? 伊拉克战争是哪些国家发动的?请快回答,我有急用! 二零零三年三月谁发动了对伊拉克的战争 西门子、美的、容声三个门的冰箱那个牌子又省电又实用? 海尔冰箱BCD-206 SCFM 放3档工作多长时间 ,停多长时间正常 海尔BCD-206SCFM基本参数 6年级上册数学练习册百分数50到53页答案 小学数学六年级(上):帮你学数学口算练习册2008年印刷版信息 小学数学六年级(上):帮你学数学口算练习册2010年印刷版信息 小学六年级数学上册百分数练习册《课堂作业本》答案64面第2题 寻求计算机专业编程:1迷宫问题的求解,要求生成迷宫矩阵,求出迷宫最短的通路(数据结构原代码) C语言(数据结构)迷宫问题 一个数据结构的迷宫的源代码问题 迷宫问题 数据结构,用C 数据结构迷宫求解代码解释,求详细解释。最好可以详细到每一句,十分感谢 怎么用不但&#39;不造句 骨折一般多长时间能长好, 太原哪家机器人教育比较好? 傲梦清少儿编程在哪里 歌菲莉女鞋加盟 歌菲莉女鞋品牌怎么样? 我女儿二十八岁生日送点什么 哥哥28岁生日送什么礼物好? 给28岁的好朋友送什么生日礼物 送28岁得男生,生日礼物,送什么比较好 想送男朋友28岁生日礼物!一定要送礼物,希望要特别点! 送28岁男人的生日礼物什么为好 送28岁得男生,生日礼物,送什么比较好? 男朋友马上28岁生日,送什么礼物好呢? 厚普股份今天股票的走势 你好,关于数据结构迷宫问题 改完以后的代码 仍存在7处错误,能麻烦您改一下嘛 ,谢谢 嘿嘿 数据结构迷宫问题 C++算法 数据结构迷宫问题求解。 请问教育科学出版社(教科版)高中物理教材全套教材都有哪几本书? 如何用数据结构创建一个20×20的迷宫,用空格和星花表示路和墙,求代码,十分感谢 严蔚敏的数据结构上的迷宫求解问题,我自己编的c代码,那位高手跟我改一下,谢谢! 高中物理教科版 理科生要学那几本? 数据结构 迷宫问题算法 请问教科版高中物理实验有哪些?? 高中物理人教版和教科版有什么不同? 跪求:怎样学好高中物理?教科版的! 请问高中物理主要教材版本的使用区域,包括但不限于人教版、教科版、粤教版、鲁教版、沪科版 教科版高中物理必修二学斜抛的要求高不高 谁知道安徽天长市国税局基层分局公务员的待遇 安徽天长市的经济怎么样啊?公务人员待遇怎么样?有谁知道。 乡镇公务员考上什么待遇? 一建考试迟到时间何时改成5分钟不能入场的 一建考试缺考是怎么算 请问 一级建造师今年考试,考试不及格和不去考试(缺考),对明年的一建考试各有什么影响呢? 一级建造师,第一年4科全部缺考,那么怎么计算滚动时间呢?还是第二年必须通过4科考试吗?