数据结构迷宫算法，第三张图中画波浪线的地方，为什么要用(k+2)%5呢？不应该是k%5吗？
数据结构 迷宫问题算法
//迷宫求解（自定义一个2维矩阵作为地图）
void Labyrinth()
{
printf("自定义迷宫矩阵：\n");
int a[10][10];
int i,j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
scanf("%d",&a[i][j]);
printf("\n");
coordinate *Laby = new coordinate[100];
int n=1;
int x,y;
Laby[1].x=x=1;
Laby[1].y=y=6;
Laby[1].step=1;
a[1][6]=2;
SqStack S;
InitStack(S);
Push(S,0);
Push(S,1);
i=1;
while(GetTop(S))
{
if(a[x][y]==100)
{
printf("找到终点了!!!\n");
break;
}
i++;
if(n==1)
a[x][y]=i;
if(a[x][y-1]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y-1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x-1][y]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x=x-1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x][y+1]==1||a[x][y+1]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y+1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x+1][y]==1||a[x+1][y]==100)
{
Push(S,i);
Laby[i].x=x=x+1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else
{
Pop(S,i);
x=Laby[i].x;
y=Laby[i].y;
a[x][y]=-1;
n=0;
}
}
if(!GetTop(S))
printf("没有找到出路!\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
printf("%d ",a[i][j]);
printf("\n");
}
}
我没有给出栈的代码，你自己应该有吧！
具体迷宫算法 就是如此 仅供参考
数据结构课程设计的迷宫问题~~~~急！！！
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>
#define N 22
#define M 22
int bg[M][N];/*用二维数组描述迷宫,bg[i][j]==1表示这格已走*/
void makebg(int,int);
void drawbg(int[][],int,int,int,int,int);
void drawman(int,int,int);
void rect(int,int,int,int);
void main(){/* main()开始 */
int step=20;
int len=10;
int size=20;
int x=0,y=0;
int i=0,j=0;
int gdriver=DETECT,gmode;
char ch;
int direc;
makebg(M,N);
/* registerbgidriver(EGAVGA_driver);*/
/* initgraph(&gdriver,&gmode,"c:\\turboc2"); */
initgraph(&gdriver,&gmode,"c:\\tc20\\bgi");/*这里是TC中要进行画线,绘图前所作的出使化工作,不是数据结构中的图*/
cleardevice();
setwritemode(XOR_PUT);
settextstyle(1,0,3);
setcolor(GREEN);
outtextxy(100,180,"Press <Q> to quit");
setcolor(BLUE);
setfillstyle(LINE_FILL,BLUE);
drawbg(bg,M,N,size,0,0);
setcolor(WHITE);
x+=len;y+=len;
drawman(x,y,len);
setcolor(GREEN);
outtextxy(60,120,"PRESS KEY <1> :YOU ,");
outtextxy(70,150,"OTHER KEY :AUTOMATIC");
setcolor(WHITE);
if((ch=getch())=='1'){
/* 人工控制 */
while((ch=getch())!='q'){
drawman(x,y,len);
switch(ch){
case 'a':
if(j>0&&bg[i][j-1]==0){
if(x>step){x-=step;j--;};
}
break;
case 's':
if(i<M-1&&bg[i+1][j]==0){
if(y<479-step){y+=step;i++;};
}
break;
case 'd':
if(j<N-1&&bg[i][j+1]==0){
if(x<639-step){x+=step;j++;}
}
break;
case 'w':
if(i>0&&bg[i-1][j]==0){
if(y>step){y-=step;i--;}
}
break;
default :break;
}
drawman(x,y,len);
delay(800);
if(i>=M-1&&j>=N-1){
settextstyle(4,0,3);
setcolor(RED);
outtextxy(150,260,"YOU WIN!");
}
setcolor(WHITE);
}
closegraph();
}/* 人工控制结束 */
else{
/* 电脑控制 */
/* direc表示上一步运动方向 */
/* 并表示下一步运动方向 */
/* 0~3分别表示 西、北、东、南 */
direc=2;
i=j=0;
while(i<M-1||j<N-1){
delay(80000);
drawman(x,y,len);
switch(direc){
case 0:
/* 以3,0,1的次序尝试 */
if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else {
x+=step;j++;
direc=2;
}
break;
case 1:
if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else{
y+=step;i++;
direc=3;
}
break;
case 2:
if(i>0&&bg[i-1][j]==0){
y-=step;i--;
direc=1;
}
else if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else {
x-=step;j--;
direc=0;
}
break;
case 3:
if(j<N-1&&bg[i][j+1]==0){
x+=step;j++;
direc=2;
}
else if(i<M-1&&bg[i+1][j]==0){
y+=step;i++;
direc=3;
}
else if(j>0&&bg[i][j-1]==0){
x-=step;j--;
direc=0;
}
else {
y-=step;i--;
direc=1;
}
break;
default :break;
}
drawman(x,y,len);
}
getch();
closegraph();
}/* 电脑控制结束 */
}/* main()结束 */
/* 绘制小人 */
void drawman(int x,int y,int len){
int r=len/4;
rect(x-r,y-len,x+r,y-len+2*r);
line(x,y-len+2*r,x,y);
line(x-len,y,x+len,y);
line(x,y,x-len,y+len);
line(x,y,x+len,y+len);
}
/* 绘制迷宫地图 */
void drawbg(int bg[][N],int a,int b,int size,int x,int y){
int startx=x;
int i,j;
for(i=0;i<a;i++){
for(j=0;j<b;j++){
if(bg[i][j]==1)
rect(x,y,x+size-1,y+size-1);
x+=size;
}
x=startx;
y+=size;
}
rectangle(0,0,size*b,size*a);
line(0,0,size,0);line(0,0,0,size);
line(size*b,size*(a-1),size*b,size*a);
line(size*(b-1),size*a,size*b,size*a);
}
/* 绘制实心矩形 */
void rect(int x0,int y0,int x1,int y1){
int i,j;
for(i=x0;i<=x1;i++)
line(i,y0,i,y1);
}
/* 随机生成代表迷宫地图的数组 */
void makebg(int a,int b){
int i,j;
int ran;
int direc;
/* 初始化迷宫地图 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
bg[i][j]=1;
/* 随机生成迷宫通路 */
randomize();
i=j=0;direc=2;
while(1){
bg[i][j]=0;
if(i>=M-1&&j>=N-1)break;
ran=(int)rand()*4;
if(ran<1){
if(direc!=1&&i<a-1){
i++;
direc=3;
}
}
else if(ran<2){
if(direc!=2&&j>0){
j--;
direc=0;
}
}
else if(ran<3){
if(direc!=3&&i>0){
i--;
direc=1;
}
}
else {
if(direc!=0&&j<b-1){
j++;
direc=2;
}
}
}
/* 随机生成迷宫其余部分 */
for(i=0;i<a;i++)
for(j=0;j<b;j++)
if(bg[i][j]==1){
ran=(int)rand()*10;
if(ran<7)bg[i][j]=0;
}
}
数据结构 迷宫问题
#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();
}
高手进啊，数据结构，迷宫问题~~
回溯的非递归框架：
x[1]=1;坐标
y[i]=1;
d[1]=0;方向 0123
k=1;
while (k>0)
{
d[k]++;
while(d[k]不符合条件)d[k]++;
if k为终点状态 print;
if d[k]越界 k--;
else k++;推算k+1的各项值;
}
照这个思路自己做吧