#include<stdio.h>
#include<stdlib.h>
#define L 6
#define V 6
#define maxsize 1024
typedef struct node /*队列中元素的类型*/
{
int x,y;
int pre;
}linklist;
typedef struct /*顺序队列的结构,没有完成循环,遗憾一*/
{
linklist a[maxsize];
int front,rear;
}linkqueue;
struct movedata /*四周偏移结构数组*/
{
int x,y;
}move[8]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
void input(); /*输入函数声明*/
void print(int *); /*打印函数声明*/
int getpath(void);
void enqueue(int ,int );
void dequeue(void);
void recovery(int *);
int data[L][V]; /*定义迷宫全局的二维数组*/
linkqueue *sq;
void main(void)
{
int x;
input(); /**/
printf("迷宫如下:\n");
print(&data[0][0]);
sq=(linkqueue *)malloc(sizeof(linkqueue));
sq->front=0;
sq->rear=sq->front;
sq->a[sq->front].x=1;
sq->a[sq->front].y=1;
sq->a[sq->rear].pre=0;
x=getpath();
if(x==0)
{
printf("该迷宫没有入口\n");
}
else
{
dequeue();
printf("更改后的迷宫如下:\n");
print(&data[0][0]);
printf("\n");
recovery(&data[0][0]);
printf("恢复迷宫,如下:\n");
print(&data[0][0]);
}
}
void input() /*输入迷宫进入二维数组*/
{
int i,j;
int *p;
p=&data[0][0];
for(i=0;i<V;i++)
{
data[0][i]=1;
}
for(i=1;i<L-1;i++)
{
data[i][0]=1;
for(j=1;j<V-1;j++)
{
scanf("%d",&data[i][j]);
}
data[i][V-1]=1;
printf("请输入下一行\n");
}
for(i=0;i<V;i++)
{
data[L-1][i]=1;
}
}
void print(int *q) /*迷宫的输入打印 水平L,竖直V*/
{
int i,j;
for(i=0;i<L;i++)
{
for(j=0;j<V;j++)
{
printf("%+1d ",*(q+i*V+j));
}
printf("\n");
}
}
int getpath(void)
{
int i;
int r1,r2;
r1=0;
r2=0;
if(data[1][1]==1)
{
return (0);
}
else
{
for(;r1!=L-1 || r2!=V-1; sq->front=(sq->front+1)%maxsize)
{
for(i=0;i<8;i++)
{
r1=sq->a[sq->front].x+move[i].x;
r2=sq->a[sq->front].y+move[i].y;
if(data[r1][r2]==0)
{
enqueue(r1,r2);
data[r1][r2]=-1;
}
}
}
return (1);
}
}
void enqueue(int m,int n) /*入队列函数*/
{
sq->rear=(sq->rear+1)%maxsize;
sq->a[sq->rear].x=m;
sq->a[sq->rear].y=n;
sq->a[sq->rear].pre=sq->front;
}
void dequeue(void) /*输出最后路径*/
{
for(;sq->a[sq->rear].x!=1 || sq->a[sq->rear].y!=1; ) /*sq->a[sq->rear].pre!=0*/
{
printf("(%d,%d) ",sq->a[sq->rear].x,sq->a[sq->rear].y);
sq->rear=sq->a[sq->rear].pre;
}
printf("(%d,%d) ",sq->a[sq->rear].x,sq->a[sq->rear].y);/*第一个数据输出问题*/
}
void recovery(int *q) /*迷宫的恢复*/
{
int i,j;
for(i=0;i<L;i++)
{
for(j=0;j<V;j++)
{
if(*(q+i*V+j)==-1)
{
*(q+i*V+j)=0;
}
}
}
}