#include"stdio.h"
void print(int front);
mgpath(int xi, int yi, int xe, int ye);
int mg[10][10]=
{ { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },{ 1, 0, 0, 0, 0, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },{ 1, 0, 1, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1, 0, 1, 1, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
int MaxSize=100;
int front=-1;
int rear=-1;
struct Qu{
int i;
int j;
int pre;}q[100];
void main(){
int M = 8;
int N = 8;
mgpath(1, 1, M, N);
}
void print(int front)
{
int k=front, j, ns=0;
printf("\n");
do
{
j = k;
k = q[k].pre;
q[j].pre = -1;
} while (k != 0);
printf("迷宫路径如下:\n");
k = 0;
while (k < 100)
{
if (q[k].pre==-1)
{
ns++;
printf("%d%3d",q[k].i,q[k].j);
if (ns % 5==0)
printf("\n");
}
k++;
}
printf("\n");
printf("队列状态");
// System.out.println("下标 i j pre");
// for(int i=0;i<=q.rear;i++)
// {
// System.out.printf("%2d %d %d %2d\n",i,q.i[i],q.j[i],q.pre[i]);
// }
}
mgpath(int xi, int yi, int xe, int ye)
{
int i, j, di;
int find=0;
rear++;
q[rear].i=xi;
q[rear].j=yi;
q[rear].pre=-1;
mg[xi][yi]=-1; // 标记入口
while (front<=rear && (!find))
{
front++;
i=q[front].i;
j=q[front].j;
if (i==xe && j==ye)
{
find=1;
print(front);
return 1;
}
for (di=0; di<4; di++)
{
switch (di)
{
case 0:
i=q[front].i - 1;
j=q[front].j;
break;
case 1:
i=q[front].i;
j=q[front].j + 1;
break;
case 2:
i=q[front].i + 1;
j=q[front].j;
break;
case 3:
i=q[front].i;
j=q[front].j - 1;
}
if (mg[i][j]==0)
{
rear++;
q[rear].i=i;
q[rear].j=j;
q[rear].pre=front;
mg[i][j]=-1;
}
}
printf("NO WAY\n");
return 0;
}