迷宫问题 输出路径
- 格式:doc
- 大小:36.50 KB
- 文档页数:3
#include
#include
typedef struct{
int line;
int row;
}pos;
typedef struct{
pos seat;
int di;
}SqStack;
SqStack S[1000];
int top;
void Initmaze(int maze[100][100],int size1,int size2) {
for(int i=1;i<=size1;i++)
{for(int j=1;j<=size2;j++)
maze[i][j]=1;
}
for(int i=2;i<=size1-1;i++)
{for(int j=2;j<=size2-1;j++)
maze[i][j]=rand()%2;
}
}
void printmaze(int maze[100][100],int size1,int size2) { for(int i=1;i<=size1;i++)
{for(int j=1;j<=size2;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void printpath(int maze[100][100],pos end)
{
printf("通道路径为");
int i;
for(i=1;i<=top;i++)
{
printf("(%d,%d) ",S[i].seat.line,S[i].seat.row);
}
printf("(%d,%d)\n",end.line,end.row);
}
int pass(int maze[100][100],pos curpos)
{ if(maze[curpos.line][curpos.row]==0)
return 1;
else return 0;
}
void FootPrint( int maze[100][100],pos pos)
{
maze[pos.line][pos.row] = 1;
}
pos nextpos(int maze[100][100],SqStack curPos) {
pos curpos=curPos.seat;
switch(curPos.di)
{
case 1:
++curpos.line;
break;
case 2:
++curpos.row;
break;
case 3:
--curpos.line;
break;
case 4:
--curpos.row;
break;
}
return curpos;
}
int MazePath(int maze[100][100],pos start,pos end) { pos curpos;
SqStack e;
top=0;
curpos=start;
e.di=1;
e.seat=curpos;
S[++top]=e;
while(top!=0)
{
curpos=nextpos(maze,e);
if(pass(maze,curpos))
{
FootPrint(maze,curpos);
if(curpos.row==end.row&&curpos.line==end.line)
return 1;
e.di=1;
e.seat=curpos;
S[++top]=e;
}
else
{
if(e.di==5)
{
e=S[--top];
}
else e.di++;
}
}
return 0;
}
void main()
{
int size1,size2,maze[100][100];
printf("输入迷宫尺寸");
scanf("%d",&size1);
scanf("%d",&size2);
Initmaze(maze,size1,size2);
printmaze(maze,size1,size2);
pos start,end;
printf("请输入入口坐标");
scanf("%d",&start.line);
scanf("%d",&start.row);
printf("请输入出口坐标");
scanf("%d",&end.line);
scanf("%d",&end.row);
if(MazePath(maze,start,end))
printpath(maze,end);
else printf("找不到通路\n");
}