c语言，运用队列的数据结构知识求解迷宫问题的最短路径步数。

Question

问题遇到的现象和发生背景

给定一迷宫以及入口和出口的坐标，要求寻找从入口到出口的最短距离。
Input
第一行两个数m和n表示迷宫的行数和列数。迷宫大小不超过45×45。

接下来是m行n列的数，用来表示迷宫，1表示墙，0表示通路。

第二行四个数x1,y1,x2,y2分别表示起点和终点的坐标。

Output
从起点到终点所经过的最短路径长度，如果不存在，输出"no path!"

Sample Input
8 8
0 0 0 0 0 0 0 1
0 1 1 1 1 0 0 0
0 1 0 1 1 1 1 0
0 1 1 0 0 0 0 0
0 0 0 1 0 1 1 1
0 1 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 1 7
Sample Output
8

问题相关代码，请勿粘贴截图

运行结果及报错内容

我的解答思路和尝试过的方法

用队列求解。

我想要达到的结果

不同于网上找到的答案的，运用c语言的知识。

Answer 1

不同于网上找到的答案的

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef struct data
{
    int x;
    int y;
    int len;
} QDataType; //数据类型

typedef struct ListNode //通过链表实现的
{
    QDataType _data;
    struct ListNode *_pNext;
} ListNode, *pListNode;

typedef struct Queue
{
    pListNode _pHead; //头指针
    pListNode _pTail; //尾指针
} Queue;

pListNode BuyNode(QDataType d)
{
    pListNode new = malloc(sizeof(ListNode));
    new->_data = d;
    new->_pNext = NULL;
    return new;
}

void QueueInit(Queue *q)
{
    assert(q);
    QDataType d;
    q->_pHead = BuyNode(d);
    q->_pTail = q->_pHead;
}

void QueuePush(Queue *q, QDataType d)
{
    assert(q);
    q->_pTail->_pNext = BuyNode(d);
    q->_pTail = q->_pTail->_pNext;
}

void QueuePop(Queue *q)
{
    pListNode dNode = q->_pHead->_pNext;
    if (dNode)
    {
        q->_pHead->_pNext = dNode->_pNext;
        if (q->_pHead->_pNext == NULL)
        {
            q->_pTail = q->_pHead;
        } //如果只有一个元素，删完后ptail会悬空
        free(dNode);
    }
}

int QueueSize(Queue *q)
{
    assert(q);
    pListNode pre = q->_pHead->_pNext;
    int count = 0;
    while (pre)
    {
        count++;
        pre = pre->_pNext;
    }
    return count;
}
int QueueEmpty(Queue *q)
{
    return NULL == q->_pHead->_pNext;
}
QDataType Front(Queue *q)
{
    return q->_pHead->_pNext->_data;
}
QDataType Back(Queue *q)
{
    return q->_pTail->_data;
}

Queue *q;
int ds[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int m, n;
int a[100][100];

int bfs(int x, int y, int x2, int y2)
{
    QDataType d = {x, y, 0};
    QueuePush(q, d);
    a[x][y] = 2;
    while (!QueueEmpty(q))
    {
        d = Front(q);
        QueuePop(q);
        for (int i = 0; i < 4; i++)
        {
            int tx = d.x + ds[i][0];
            int ty = d.y + ds[i][1];
            if (tx == x2 && ty == y2)
            {
                return d.len+1;
            }
            if (tx >= 0 && tx < m && ty >= 0 && ty < n && a[tx][ty] == 0)
            {
                QDataType t = {tx, ty, d.len+1};
                QueuePush(q, t);
                a[tx][ty] = 2;
           }
        }
    }
    return 0;
}

int main()
{
    int x1, y1, x2, y2;
    int i, j;
    q = (Queue *)malloc(sizeof(Queue));
    QueueInit(q);
    scanf("%d %d", &m, &n);
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    }
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    int len = bfs(x1, y1, x2, y2);
    if (len>0)
    {
        printf("%d", len);
    }
    else
    {
        printf("no path!");
    }
    return 0;
}