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;
}

Answer 2

#include <iostream>
#include <algorithm>
using namespace std;
int findMinRoad(int road[100][100],int x0, int y0,int x1,int y1);
int main()
{
    int row,col;
       int x0,y0,x1,y1;
    int road[100][100];
    cin>>row>>col;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin>>road[i][j];
    cin>>x0>>y0>>x1>>y1;
    int ans;
    ans = findMinRoad(road,x0, y0,x1,y1);
    if(ans == -1)
        cout<<"no path!";
    else
        cout<<ans;
   return 0;
}
// 利用动态规划求解
int findMinRoad(int road[100][100],int x0, int y0,int x1,int y1){
        // 辅助一维数组
        int path[y1-y0+1];
        int MAX = 99999;
        // 初始化
        path[0] = road[x0][y0] == 1 ? MAX : 0;
        for (int i = y0+1; i <= y1; i++)
            path[i-y0] = road[x0][i] == 1 ? MAX : path[i-y0-1]+1;
        // 到达各位置的最短路径
        for (int i = x0+1; i <= x1; i++) 
        {
            if (road[i][y0] == 0)
            {
                path[0] += 1;
            }else
            {
                path[0] = MAX;
            }
            for (int j = y0+1; j <=y1 ; j++)
            {
                if (road[i][j] == 0)//有路
                {
                    // 到达当前位置的最短路径 = 
                    //        min(到达左边一个位置的最短路径+1，到达上面一个位置的最短路径+1)
                    path[j-y0] = min(path[j-y0-1]+1,path[j-y0]+1);
                }else// 墙
                {
                    path[j-y0] = MAX;//无法到达该位置
                }
            }
        }
        return path[y1-y0] >= MAX ? -1 : path[y1-y0];
    }

Answer 3

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632

Answer 4

这个很简单