甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
#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;irow+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;iline+2;i++) /*将迷宫的四周都变为1*/
maze[0][i]=1;
for(i=0;iline+2;i++)
maze[row+1][i]=1;
for(i=0;irow+2;i++)
maze[i][0]=1;
for(i=0;irow+2;i++)
maze[i][line+1]=1;
for(i=0;irow+2;i++) /*输出迷宫*/
{
for(j=0;jline+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==rb==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==rb==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==rb==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==rb==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();
}
这个可以用 堆栈 来完成。
用堆栈的基本思路就是。
设置一个起点A。将 A 入栈 。
从A开始找到第一个可以达到的点B。将 B 入栈 。
如果B无路可走。则在A点处重新换一个可达到的点。否则继续 2-3 。直到达到终点。或者五路可走。
详细的解释，这儿有一篇博文：
很简单，这是一个回溯的搜索，
if(maze[x+move[i].x][y+move[i].y]==0)
if(path(maze,move,x+move[i].x,y+move[i].y,step))
这两句的意思是说如果迷宫的maze[x+move[i].x][y+move[i].y]这个位置可以走，那么下一次就从这个位置开始。
step--;
maze[x][y]=0;
这两句是在选择的路径是死路的时候用来撤销标记，返回出发点的语句
如图是我修改他人代码得到的。因为C画面的墙和路都要占同样1格。
如果画偶数宽高则会有路径浪费，所以还是画奇数宽高的好。
部分代码如下:(完整代码请追问)
int main()
{
int i,j;
system("color 2b");
srand((unsigned)time(NULL)); /*初始化随即种子*/
hidden(); /*隐藏光标*/
for(i=0;i=Height+1;i++)
for(j=0;j=Width+1;j++)
if(i==0||i==Height+1||j==0||j==Width+1) /*初始化迷宫*/
map[i][j]=Road;
else map[i][j]=Wall;
create(2*(rand()%(Height/2)+1),2*(rand()%(Width/2)+1)); /*从随机一个点开始生成迷宫*/
for(i=0;i=Height+1;i++) /*边界处理*/
{
map[i][0]=Wall;
map[i][Width+1]=Wall;
}
for(j=0;j=Width+1;j++) /*边界处理*/
{
map[0][j]=Wall;
map[Height+1][j]=Wall;
}
//★百度知道“q839219286”修订，多画一格避免宽高为偶数时没有墙
{ int pH_even= (Height/2)*2, pW_even=(Width/2)*2; //宽高偶数化
map[2][1]=Start; /*给定入口*/
map[pH_even][Width]=End; /*给定出口*/
for(i=1;i=pH_even+1;i++) /*画出迷宫*/
for(j=1;j=pW_even+1;j++)
paint(i,j);
}
game(); /*开始游戏*/
return 0;
}