张恒13031028second.c

迷宫求解

#include<stdlib.h>
#include<stdio.h>
 struct  postype 
{int x;
int y;
} begin,end;
typedef struct postype posit;
#define MAXLENGTH 100
typedef int  mazetype[MAXLENGTH][MAXLENGTH];
mazetype m;

int x,y,i,j;
 print()
{int i,j;
for(i=0;i<x;i++)
{for(j=0;j<y;j++)
printf("%3d",m[i][j]);
printf("\n");
}}
void init(int k)
{int i,j,x1,y1;
printf("请输入迷宫的行数和列数：");
scanf("%d,%d",&x,&y);

for(i=0;i<x;i++)
{m[0][i]=0;
m[x-1][1]=0;}

for(i=0;i<y-1;i++)
{m[i][0]=0;
m[i][y-1]=0;}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=k;
printf("请个数输入迷宫内墙的个数:\n");
scanf("%d",&j);
printf("请依次输入内墙的行数和列数:\n");
for(i=1;i<=j;i++)
{scanf("%d,%d",&x1,&y1);
m[x1][y1]=0;
}
printf("迷宫的结构如下:\n");
print();
printf("请输入迷宫的入口的行数和列数:");
scanf("%d,%d",&begin.x,&begin.y);
printf("请输入迷宫的出口的行数和列数：");
scanf("%d,%d",&end.x,&end.y);}

 extern int curstep=1;
  struct eltype
{int ord;
posit seat;
int di;
};
 typedef  struct eltype quzzle;
 pass(posit b)
{if(m[b.x][b.y]==1)
return 1;
 else return 0;}


footprint(posit a)
{m[a.x][a.y]=curstep;/*使迷宫的M的A点的值变为足迹*/
}
posit nextpos(posit c,int di)
{posit direc[4]={{0,1},{1,0},{0,-1},{-1,0}};/*移动的方向，依次为东南西北*/
c.x+=direc[di].x;
c.y+=direc[di].y;
return c;
}
markprint(posit b)
{m[b.x][b.y]=-1;}/*把迷宫的B点变为-1（表示不能通过的路径）*/
quzzle s[MAXLENGTH];
int top=-1;
posit curpos;
quzzle e;

mazepath(posit start,posit end)
{/*若迷宫中有从入口到出口的路径，则求出放在栈中，并返回TURE；否则则返回FALSE*/
quzzle s[MAXLENGTH];
int top=-1;
posit curpos;
quzzle e;


curpos=start;curstep=1;
do{
	if (pass(curpos)){
footprint(curpos);
e.ord=curstep;
e.seat=curpos;
e.di=0;
if(top>=MAXLENGTH)
{printf("栈的内容已满\n");
return -1;}
top++;
s[top]=e;
curstep++;
if(curpos.x==end.x&&curpos.y==end.y)
return 1;
    nextpos(curpos,e.di);}
else
{if(top!=-1)
{	 if(top<0)
{printf("栈的内容是空的\n");
return -1;}

top--;
curstep--;
while(e.di==3)
{markprint(e.seat);
	 if(top<0)
{printf("栈的内容是空的\n");
return -1;}

top--;
curstep--;
}   
if(e.di<3)
{e.di++;
if(top>=MAXLENGTH)
{printf("栈的内容已满\n");
return -1;}
top++;
s[top]=e;
curstep++;
curpos=e.seat;
nextpos(curpos,e.di);
}}}}
while(top!=-1);
return 0;}

main()
{init(1);
if(mazepath(begin,end))
{print();
}
else printf("no path\n");
}