杭州交通信息网常务委员会委员有谁:C++编写的迷宫问题
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/11 00:25:56
用MXN数组表示迷宫。0表示可通过，1表示不通。
每一个位置上，课选择的又8个方向之一，每个方向有一个编号设当前位置为（i，j）则下一个位置应该在迷宫范围内，位置为（i+1，j+1）（k、l为－1，＋1）的0值方程，为省去判别是否越界的负担，在迷宫外围加一圈元素，值均为1。对于MXN迷宫，使用的数组有（M＋2）行（N＋2）列，是是定入口为左上角元素，出口为右下角元素。走迷宫采用回溯技术，在每个有多出路的位置上采用约定的策略选择一个出路，如果尚未找到出口，遇到无进路的位置则应返回最近的一个分支点重新选择出路。
在每个位置上处理方法如下：若知当前位置已经是出口，则表示已经成功，否则计算当前出口数，已经走过位置应排除。将经过的位置值改为非0，若出口数字为1，iaoshi无选择，直接推经，若出口数大于1，镜当前信息送入数组中。
当前位置信息除行列号外还包括一个方向值，规定找出路时，总是从0方向开始顺时针进行在数组内保存了每个分支上已经选过方向的最大值，这样回溯时不必从0开始。
大家好，我是一个菜鸟，现在正在学习数据结构，希望大家指点我，我编写了一个走迷宫的程序，希望大家指点。源程序如下：（可以动态实现）
#include"time.h"
#include "stdio.h"
#include "graphics.h"
#include "conio.h"
#define null 0
int a[11][15]={ {1,0,1,1,1,0,0,1,1,1,0,0,0,0,0}, /定义迷宫，这是我们课程设计，所以就用老师给的了/
{0,1,1,1,0,0,1,0,0,0,0,1,1,0,0}, /0代表墙，1代表可以通行/
{1,0,0,1,1,1,1,0,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,1,0,0,0,1,0,1,1},
{0,0,1,0,1,1,0,1,0,0,0,0,0,0,0},
{1,1,0,0,1,0,0,0,1,0,1,1,0,0,0},
{1,0,0,0,0,1,1,0,0,0,0,0,0,0,0},
{1,1,0,0,1,0,0,1,0,0,0,0,0,1,0},
{0,0,1,1,1,0,0,1,0,0,1,1,1,1,1},
{1,1,0,0,0,0,0,1,1,1,0,0,0,0,1},
{1,0,1,1,0,0,0,0,0,1,0,0,0,0,1}
};
struct moving /定义走动方向/
{int x;
int y;
}move[9]={{0,0},{1,1},{0,1},{1,0},{-1,1},{1,-1},{-1,0},{0,-1},{-1,-1}};
typedef struct Position *PPosition;
struct Position /定义结构体/
{
int x;
int y;
int direction;
PPosition link;
};
struct LinkPosition /引入一层封装，其实就是好定义空栈罢了/
{
PPosition top;
};
typedef struct LinkPosition *PLinkPosition;
PLinkPosition createEmptyPosition(void) /建立空栈/
{
PLinkPosition plposition;
plposition=(PLinkPosition)malloc(sizeof(struct LinkPosition));
plposition->top=null;
return(plposition);
}
void push(PLinkPosition plposition,int x,int y) /压栈/
{
PPosition p;
p=(PPosition)malloc(sizeof(struct Position));
p->x=x;
p->y=y;
p->direction=1;
p->link=plposition->top;
plposition->top=p;
}
void pop(PLinkPosition plposition) /弹栈/
{
PPosition p;
p=plposition->top;
plposition->top=plposition->top->link;
free(p);
}
int judge(PLinkPosition plposition) /判断这个位置是不是栈中已有的/
{int m,n;
PPosition p;
m=plposition->top->x;
n=plposition->top->y;
p=plposition->top->link;
while(p!=null)
{if(p->x!=m||p->y!=n)p=p->link;
else
{return(0);
break;
}
}
return(1);
}
void maze(void) /画迷宫/
{
int i,j;
setbkcolor(1);
setcolor(4);
rectangle(90,50,540,380);
for(i=80;i<380;i=i+30)
line(90,i,540,i);
for(i=120;i<540;i=i+30)
line(i,50,i,380);
for(i=0;i<11;i++)
{for(j=0;j<15;j++)
if(a[i][j]==1)floodfill(105+j*30,65+i*30,4);
};
}
void erasermouse(PLinkPosition plposition) /擦除所走过的点/
{
int x1,y1;
x1=105+30*(plposition->top->y-1);
y1=65+30*(plposition->top->x-1);
setcolor(15);
line(x1-10,y1,x1+10,y1);
line(x1,y1-10,x1,y1+10);
setcolor(4);
}
void mouse(PLinkPosition plposition) /画出当前位置/
{
int x1,y1;
x1=105+30*(plposition->top->y-1);
y1=65+30*(plposition->top->x-1);
line(x1-10,y1,x1+10,y1);
line(x1,y1-10,x1,y1+10);
}
void TIMEDELAY() /时间延迟函数，这样动态实现时才可以看清/
{
clock_t time;
time=5+clock();
while(time>clock());
}
main()
{
PLinkPosition plposition,answer;
PPosition p;
int i,j,d,m,n,m1,n1,x1,y1,driver=VGA,mode=VGAHI;
int c[13][17]={0};
clock_t times;
initgraph(&driver,&mode,"");
for(i=1;i<12;i++)
for(j=1;j<16;j++)
c[i][j]=a[i-1][j-1]; /c数组就是给迷宫外层加了一层墙/
plposition=createEmptyPosition();
plposition->top->link=null;
push(plposition,1,1); /压入初始点/
maze();
mouse(plposition);
TIMEDELAY();
erasermouse(plposition);
a: /主结构判断并找出路径/
for(i=plposition->top->direction;i<=9;i++)
{
if(i==9)
{c[plposition->top->x][plposition->top->y]=0;
pop(plposition);
mouse(plposition);
TIMEDELAY();
erasermouse(plposition);
goto a;
}
m=plposition->top->x;
n=plposition->top->y;
m1=m+move[i].x;
n1=n+move[i].y;
push(plposition,m1,n1);
if(c[m1][n1]==0)
{pop(plposition);
plposition->top->direction++;
continue;
}
if(judge(plposition)==0)
{
pop(plposition);
continue;
}
mouse(plposition);
TIMEDELAY();
erasermouse(plposition);
if(m1==11&&n1==15)break;
goto a;
}
answer=createEmptyPosition(); /由于栈中元素弹出时是从出口到入口的路径，所以把它们反过来/
p=plposition->top;
while(p!=null)
{m=p->x;
n=p->y;
push(answer,m,n);
p=p->link;
}
p=answer->top;
for(i=1;i<25;i++)
printf("\n");
while(p->link!=null)
{printf("(%d,%d)-->",p->x,p->y);p=p->link;}
printf("(%d,%d)",p->x,p->y);
getch();
}