数据结构 迷宫问题

Question

学校课程设计题目，两个星期内交，无奈鄙人能力有限还想毕业...

迷宫问题

设计内容
编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程给出通过路径或无法通行的信息。
算法输入：代表迷宫入口的坐标
算法输出：穿过迷宫的结果。
算法要点：创建迷宫，试探法查找路径，输出解

要用C++结构简单，不要求高级功能，最佳200分
最好用C++和栈做

Answer 1

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

typedef struct pos /*描述迷宫当前位置和方向*/
{
int x;
int y;
int way; /*0:无效,1:左,2:下,3:右,4:上*/
}P;

typedef struct LinkNode /*链表结构,用于栈的元素类型*/
{
P pos;
struct LinkNode *next;
}LinkNode;

typedef struct stack /*链式栈,用于存储迷宫路径信息*/
{
LinkNode *head; /*头指针*/
}Stack;

int row=0; /*迷宫的行数*/
int line=0; /*迷宫的列数*/

void InitStack(Stack *s) /*栈置空*/
{
s->head=NULL;
}

void Push(Stack *s,P p) /*数据入栈*/
{
LinkNode *LN=(LinkNode *)malloc(sizeof(LinkNode));
LN->pos=p;
LN->next=s->head;
s->head=LN;
}

P Pop(Stack *s) /*栈顶元素出栈*/
{
P pos;
LinkNode *LN;
LN=s->head;
s->head=s->head->next;
pos=LN->pos;
delete LN;
return pos;
}

P GetPop(Stack s) /*读取栈顶元素*/
{
return s.head->pos;
}

int Empty(Stack s) /*判空*/
{
if(s.head==NULL)
return 1;
else
return 0;
}

int **InitMaze() /*返回迷宫的二维指针*/
{
int **maze=NULL;
int i;
int j;
printf("请输入迷宫的行跟列(x,y):");
scanf("%d,%d",&row,&line); /*输入迷宫的行和列*/
maze=(int **)malloc((row+2)*sizeof(int *));
for(i=0;i<row+2;i++)
{
maze[i]=(int *)malloc(sizeof(int)*(line+2));
}
printf("请输入迷宫\n"); /*输入迷宫,1代表路障,0代表通行*/
for(i=1;i<=row;i++)
for(j=1;j<=line;j++)
scanf("%d",&maze[i][j]);
for(i=0;i<line+2;i++) /*将迷宫的四周都变为1*/
maze[0][i]=1;
for(i=0;i<line+2;i++)
maze[row+1][i]=1;
for(i=0;i<row+2;i++)
maze[i][0]=1;
for(i=0;i<row+2;i++)
maze[i][line+1]=1;
for(i=0;i<row+2;i++) /*输出迷宫*/
{
for(j=0;j<line+2;j++)
printf("%3d",maze[i][j]);
printf("\n");
}
return maze;
}

void PrintWay(Stack p) /*输出路径*/
{
P pos;
Stack t; /*临时栈,用于存储从入口到出口的路径*/
LinkNode *temp;
int a,b;
InitStack(&t);
temp=(LinkNode *)malloc(sizeof(LinkNode));
temp->pos=Pop(&p); /*取栈顶元素,即出口*/
Push(&t,temp->pos); /*入栈*/
free(temp);
while(!Empty(p))
{
temp=(LinkNode *)malloc(sizeof(LinkNode));
temp->pos=Pop(&p); /*获取下一个元素*/
a=GetPop(t).x-temp->pos.x; /*左:a=0,b=1; 下:a=1,b=0*/
b=GetPop(t).y-temp->pos.y; /*右:a=0,b=-1 上:a=-1,b=0;*/
if(b==1)
temp->pos.way=1;
else if(a==1)
temp->pos.way=2;
else if(b==-1)
temp->pos.way=3;
else if(a==-1)
temp->pos.way=4;
Push(&t,temp->pos); /*新位置入栈*/
free(temp);
}
printf("迷宫的路径为:\n");
printf("前两个数字表示位置,最后一个数字表示方向\n");
printf("1表示向左,2表示向下,3表示向右,4表示向上,0表示无方向\n");
while(!Empty(t)) /*输出路径*/
{
pos=Pop(&t);
printf("%3d,%3d,%3d\n",pos.x,pos.y,pos.way);
}
}

int FindMaze(int **maze,int r,int l) /*寻找路径,找到返回1,没找到返回0*/
{
Stack p,q; /*栈p,q分别表示探索迷宫的路径和过程*/
P temp1,temp2;
int a,b;
InitStack(&p);
InitStack(&q);
temp1.x=1;
temp1.y=1; //
maze[1][1]=-1; /*标记已经走过*/
Push(&p,temp1);
Push(&q,temp1);
while(!Empty(q))
{
temp2=GetPop(q);
if(!(GetPop(p).x==GetPop(q).x
&&GetPop(p).y==GetPop(q).y))
Push(&p,temp2); /*若有新元素入栈,就把q的栈顶元素存入p中*/
a=temp2.x;
b=temp2.y+1; /*当前位置左方向相邻的方块*/
if(maze[a][b]==0)
{
temp1.x=a;
temp1.y=b;
maze[a][b]=-1; /*标记已走过*/
Push(&q,temp1);
}
if(a==r&&b==l) /*到达出口*/
{
temp1.way=0;
Push(&p,temp1);
PrintWay(p);
return 1;
}
a=temp2.x+1;
b=temp2.y; /*当前位置下方向相邻的方块*/
if(maze[a][b]==0)
{
temp1.x=a;
temp1.y=b;
maze[a][b]=-1; /*标记已走过*/
Push(&q,temp1);
}
if(a==r&&b==l) /*到达出口*/
{
temp1.way=0;
Push(&p,temp1);
PrintWay(p);
return 1;
}
a=temp2.x;
b=temp2.y-1; /*当前位置右方向相邻的方块*/
if(maze[a][b]==0)
{
temp1.x=a;
temp1.y=b;
maze[a][b]=-1; /*标记已走过*/
Push(&q,temp1);
}
if(a==r&&b==l) /*到达出口*/
{
temp1.way=0;
Push(&p,temp1);
PrintWay(p);
return 1;
}
a=temp2.x-1;
b=temp2.y; /*当前位置上方向相邻的方块*/
if(maze[a][b]==0)
{
temp1.x=a;
temp1.y=b;
maze[a][b]=-1; /*标记已走过*/
Push(&q,temp1);
}
if(a==r&&b==l) /*到达出口*/
{
temp1.way=0;
Push(&p,temp1);
PrintWay(p);
return 1;
}
if(GetPop(p).x==GetPop(q).x
&&GetPop(p).y==GetPop(q).y) /*若四个方向都走不通,则数据出栈,退回一格*/
{
Pop(&p);
Pop(&q);
}
}
return 0; /*探索迷宫失败*/
}

void main()
{
int **maze=InitMaze(); /*初始化迷宫*/
if(FindMaze(maze,row,line)) /*探索路径*/
printf("路径探索成功!\n");
else
printf("路径探索失败!\n");
getch();
}本回答被提问者采纳

Answer 2

计算机问题啊。。。。真的不懂。。。。懂这些的都是人才

Answer 3

兄弟，我的给你，回溯法
#include<stdio.h>
const int N=8;
int map[N][N];
int fp[N][N];
int dx[4]={-1 , 1, 0 , 0};
int dy[4]={0, 0 , -1 , 1};
bool ok(int i ,int j)
{
if(i>=0&&j>=0&&i<N&&j<N&&map[i][j]&&!fp[i][j])
return true ;
else return false;
}

void dfs(int x,int y)
{
int k,i,j;
if(x==N-1&&y==N-1)
{
fp[N-1][N-1]=1;
for(i=0 ; i<N ; i++)
{
for(j=0 ; j<N ; j++)
printf("%d ",fp[i][j]);
printf("\n");
}
printf("\n");
}
else
{
if(ok(x , y))
{

fp[x][y]=1;
for(k=0 ; k<4 ; k++)
{
dfs(x+dx[k] , y+dy[k]);
}
fp[x][y]=0;
}
}
}

int main(void)
{
int i,j,n;
for(i=0 ; i<N ; i++)
for(j=0 ; j<N ; j++)
{
scanf("%d",&n);
map[i][j]=n;
}
printf("******************************\n");
dfs(0,0);
return 0;
}

Answer 4

一楼的哥们回答的不错。我看行。