qazwsxedc1267834 2022-06-13 22:08 采纳率: 100%

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

Input

Output

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

• 写回答

#### 4条回答默认 最新

• 关注

不同于网上找到的答案的

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

``````
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

• 系统已结题 6月22日
• 已采纳回答 6月14日
• 创建了问题 6月13日

#### 悬赏问题

• ¥15 软件供应链安全是跟可靠性有关还是跟安全性有关？
• ¥15 电脑蓝屏logfilessrtsrttrail问题
• ¥20 关于wordpress建站遇到的问题！(语言-php)（相关搜索：云服务器）
• ¥15 【求职】怎么找到一个周围人素质都很高不会欺负他人，并且未来月薪能够达到一万以上（技术岗）的工作？希望可以收到写有具体，可靠，已经实践过了的路径的回答？
• ¥15 Java+vue部署版本反编译
• ¥100 对反编译和ai熟悉的开发者。
• ¥15 带序列特征的多输出预测模型
• ¥15 Python 如何安装 distutils模块
• ¥15 关于#网络#的问题：网络是从楼上引一根网线下来，接了2台傻瓜交换机，也更换了ip还是不行
• ¥15 资源泄露软件闪退怎么解决？