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 _pTail; //尾指针
} Queue;

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

void QueueInit(Queue *q)
{
assert(q);
QDataType d;
}

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

void QueuePop(Queue *q)
{
if (dNode)
{
{
} //如果只有一个元素，删完后ptail会悬空
free(dNode);
}
}

int QueueSize(Queue *q)
{
assert(q);
int count = 0;
while (pre)
{
count++;
pre = pre->_pNext;
}
return count;
}
int QueueEmpty(Queue *q)
{
}
QDataType Front(Queue *q)
{
}
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 ad软件 pcb布线pcb规则约束编辑器where the object matpcb布线pcb规则约束编辑器where the object matchs怎么没有+15v只有no net
• ¥15 虚拟机vmnet8 nat模式可以ping通主机，主机也能ping通虚拟机，但是vmnet8一直未识别怎么解决，其次诊断结果就是默认网关不可用
• ¥20 求各位能用我能理解的话回答超级简单的一些问题
• ¥15 yolov5双目识别输出坐标代码报错
• ¥15 这个代码有什么语法错误
• ¥15 给予STM32按键中断与串口通信
• ¥15 使用QT实现can通信
• ¥15 关于sp验证的一些东西，求告知如何解决，
• ¥35 关于#javascript#的问题：但是我写的只能接码数字和字符，帮我写一个解码JS问题