#include <stdio.h>
#define m 6
#define n 8
#define num m *n
typedef struct
{
int x, y;
int pre;
} sqtype;
int maze[m + 2][n + 2] =
{{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1},
{1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 1, 1},
{1, 1, 0, 0, 1, 1, 0, 0, 1, 1},
{1, 0, 1, 1, 0, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
typedef struct
{
int dx;
int dy;
} moved;
void printpath(sqtype sq[], int rear)
{
int i;
i = rear;
do
{
printf("(%d,%d)?", sq[i].x, sq[i].y);
i = sq[i].pre;
} while (i != -1);
}
void restore(int maze[m + 2][n + 2])
{
int i, j;
for (i =m+1; i>0; i--)
{
for (j =n+1; j >0; j--)
{
if (maze[i][j] == -1)
{
maze[i][j] = 0;
}
}
}
}
int shortpath(int maze[m+2][n+2], moved move[8])
{
sqtype sq[num];
int front, rear;
int x, y, i, j, v;
front = rear = 0;
sq[0].x = 1;
sq[0].y = 1;
sq[0].pre = -1;
maze[1][1] = -1;
while (front <= rear)
{
x = sq[front].x;
y = sq[front].y;
for (v = 0; v < 8; v++)
{
i = x + move[v].dx;
j = x + move[v].dy;
if (maze[i][j] == 0)
{
rear++;
sq[rear].x = i;
sq[rear].y = j;
sq[rear].pre = front;
maze[i][j] = -1;
}
if (i == m && j == n)
{
printpath(sq, rear);
restore(maze);
}
front++;
}
}
}
int main()
{
moved move[8];
shortpath(maze, move);
}