C语言使用广度优先搜索算法解决迷宫问题（队列）

本文实例讲述了C语言使用广度优先搜索算法解决迷宫问题。分享给大家供大家参考，具体如下：

变量 head 和 tail 是队头和队尾指针， head 总是指向队头， tail 总是指向队尾的下一个元素。每个点的 predecessor 成员也是一个指针，指向它的前趋在 queue 数组中的位置。如下图所示：

广度优先是一种步步为营的策略，每次都从各个方向探索一步，将前线推进一步，图中的虚线就表示这个前线，队列中的元素总是由前线的点组成的，可见正是队列先进先出的性质使这个算法具有了广度优先的特点。广度优先搜索还有一个特点是可以找到从起点到终点的最短路径，而深度优先搜索找到的不一定是最短路径。

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, col, predecessor; } queue[512];
int head = 0, tail = 0;
void enqueue(struct point p)
{
  queue[tail++] = p;
}
struct point dequeue(void)
{
  return queue[head++];
}
int is_empty(void)
{
  return head == tail;
}
int maze[MAX_ROW][MAX_COL] = {
  0, 1, 0, 0, 0,
  0, 1, 0, 1, 0,
  0, 0, 0, 0, 0,
  0, 1, 1, 1, 0,
  0, 0, 0, 1, 0,
};
void print_maze(void)
{
  int i, j;
  for (i = 0; i < MAX_ROW; i++) {
    for (j = 0; j < MAX_COL; j++)
    printf("%d ", maze[i][j]);
    putchar('\n');
  }
  printf("*********\n");
}
void visit(int row, int col)
{
  struct point visit_point = { row, col, head-1 };
  maze[row][col] = 2;
  enqueue(visit_point);
}
int main(void)
{
  struct point p = { 0, 0, -1 };
  maze[p.row][p.col] = 2;
  enqueue(p);
  while (!is_empty()) {
    p = dequeue();
    if (p.row == MAX_ROW - 1 /* goal */
    && p.col == MAX_COL - 1)
    break;
    if (p.col+1 < MAX_COL /* right */
    && maze[p.row][p.col+1] == 0)
    visit(p.row, p.col+1);
    if (p.row+1 < MAX_ROW /* down */
    && maze[p.row+1][p.col] == 0)
    visit(p.row+1, p.col);
    if (p.col-1 >= 0 /* left */
    && maze[p.row][p.col-1] == 0)
    visit(p.row, p.col-1);
    if (p.row-1 >= 0 /* up */
    && maze[p.row-1][p.col] == 0)
    visit(p.row-1, p.col);
    print_maze();
  }
  if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
  {
    printf("(%d, %d)\n", p.row, p.col);
    while (p.predecessor != -1) {
      p = queue[p.predecessor];
      printf("(%d, %d)\n", p.row, p.col);
    }
  } else
  printf("No path!\n");
  return 0;
}

运行结果如下：

[root@localhost arithmetic]# ./maze2.out
2 1 0 0 0
2 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 0 0 0
2 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
2 0 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 0 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 2 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 0 1 0
*********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 0 1 0
*********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 2 1 0
*********
2 1 2 0 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
(4, 4)
(3, 4)
(2, 4)
(2, 3)
(2, 2)
(2, 1)
(2, 0)
(1, 0)
(0, 0)

希望本文所述对大家C语言程序设计有所帮助。

# C语言  # 广度优先搜索  # 算法  # 迷宫问题  # 队列  # C语言实现走迷宫  # C语言数据结构之迷宫求解问题  # C语言数据结构之迷宫问题  # C语言实现数据结构迷宫实验  # 基于C语言实现的迷宫算法示例  # C语言使用深度优先搜索算法解决迷宫问题(堆栈)  # C语言 数据结构中求解迷宫问题实现方法  # 基于C语言实现简单的走迷宫游戏  # 基于C语言实现的迷宫游戏代码  # C语言通过栈实现小人走迷宫  # 最短  # 是一种  # 是由  # 步步为营  # 给大家  # 还有一个  # 所示  # 每次都  # 可以找到  # 所述  # 图中  # 点到  # 如下图  # 组中  # 特点是  # 讲述了  # goal  # main  # amp  # left 

相关文章： 制作网站哪家好,cc、.co、.cm哪个域名更适合做网站？  电影网站制作价格表,那些提供免费电影的网站，他们是怎么盈利的？  装修招标网站设计制作流程,装修招标流程？  如何快速选择适合个人网站的云服务器配置？  平台云上自助建站如何快速打造专业网站？  如何在阿里云ECS服务器部署织梦CMS网站？  整人网站在线制作软件,整蛊网站退不出去必须要打我是白痴才能出去？  建站中国官网：模板定制+SEO优化+建站流程一站式指南  用v-html解决Vue.js渲染中html标签不被解析的问题  网站制作软件有哪些,制图软件有哪些？  相册网站制作软件,图片上的网址怎么复制？  网站制作费用多少钱,一个网站的运营，需要哪些费用？  详解免费开源的.NET多类型文件解压缩组件SharpZipLib（.NET组件介绍之七）  建站之星代理费用多少？最新价格详情介绍  微信小程序 input输入框控件详解及实例（多种示例）  上海网站制作网页,上海本地的生活网站有哪些？最好包括生活的各个方面的？  建站之星ASP如何实现CMS高效搭建与安全管理？  制作国外网站的软件,国外有哪些比较优质的网站推荐？  h5在线制作网站电脑版下载,h5网页制作软件？  如何正确选择百度移动适配建站域名？  制作网站软件推荐手机版,如何制作属于自己的手机网站app应用？  ppt在线制作免费网站推荐,有什么下载免费的ppt模板网站？  c++如何打印函数堆栈信息_c++ backtrace函数与符号名解析【方法】  太平洋网站制作公司,网络用语太平洋是什么意思？  网站制作壁纸教程视频,电脑壁纸网站？  建站之星后台密码遗忘如何找回？  C#怎么使用委托和事件 C# delegate与event编程方法  建站之星后台密码遗忘？如何快速找回？  微信推文制作网站有哪些,怎么做微信推文，急？  如何选择高效可靠的多用户建站源码资源？  小捣蛋自助建站系统：数据分析与安全设置双核驱动网站优化  如何通过商城免费建站系统源码自定义网站主题？  小自动建站系统：AI智能生成+拖拽模板，多端适配一键搭建  实现点击下箭头变上箭头来回切换的两种方法【推荐】  如何通过建站之星自助学习解决操作问题？  如何在阿里云香港服务器快速搭建网站？  宁波自助建站系统如何快速打造专业企业网站？  建站之星如何通过成品分离优化网站效率？  教学网站制作软件,学习*后期制作的网站有哪些？  建设网站制作价格,怎样建立自己的公司网站？  高端建站三要素：定制模板、企业官网与响应式设计优化  宝塔新建站点为何无法访问？如何排查？  再谈Python中的字符串与字符编码（推荐）  ,网站推广常用方法？  如何通过宝塔面板实现本地网站访问？  建站之星安全性能如何？防护体系能否抵御黑客入侵？  ,购物网站怎么盈利呢？  宝盒自助建站智能生成技巧：SEO优化与关键词设置指南  利用JavaScript实现拖拽改变元素大小  制作宣传网站的软件,小红书可以宣传网站吗？