C语言使用深度优先搜索算法解决迷宫问题(堆栈)

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

深度优先搜索

伪代码

（Pseudocode）如下：

将起点标记为已走过并压栈;
while (栈非空) {
从栈顶弹出一个点p;
if (p这个点是终点)
break;
否则沿右、下、左、上四个方向探索相邻的点
if (和p相邻的点有路可走，并且还没走过)
将相邻的点标记为已走过并压栈，它的前趋就是p点;
}
if (p点是终点) {
打印p点的坐标;
while (p点有前趋) {
p点 = p点的前趋;
打印p点的坐标;
}
} else
没有路线可以到达终点;

C语言代码：

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, col; } stack[512];
int top = 0;
void push(struct point p)
{
  stack[top++] = p;
}
struct point pop(void)
{
  return stack[--top];
}
int is_empty(void)
{
  return top == 0;
}
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");
}
struct point predecessor[MAX_ROW][MAX_COL] = {
  {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
  {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
  {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
  {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
  {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};
void visit(int row, int col, struct point pre)
{
  struct point visit_point = { row, col };
  maze[row][col] = 2;
  predecessor[row][col] = pre;
  push(visit_point);
}
int main(void)
{
  struct point p = { 0, 0 };
  maze[p.row][p.col] = 2;
  push(p);
  while (!is_empty()) {
    p = pop();
    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, p);
    if (p.row+1 < MAX_ROW /* down */ && maze[p.row+1][p.col] == 0)
      visit(p.row+1, p.col, p);
    if (p.col-1 >= 0 /* left */ && maze[p.row][p.col-1] == 0)
      visit(p.row, p.col-1, p);
    if (p.row-1 >= 0 /* up */  && maze[p.row-1][p.col] == 0)
      visit(p.row-1, p.col, p);
    print_maze();
  }
  if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
  {
    printf("(%d, %d)\n", p.row, p.col);
    while (predecessor[p.row][p.col].row != -1) {
      p = predecessor[p.row][p.col];
      printf("(%d, %d)\n", p.row,
      p.col);
    }
  } else
    printf("No path!\n");
    return 0;
}

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

赞 (0)

相关推荐

  • C语言实现二叉树的搜索及相关算法示例

    本文实例讲述了C语言实现二叉树的搜索及相关算法.分享给大家供大家参考,具体如下: 二叉树(二叉查找树)是这样一类的树,父节点的左边孩子的key都小于它,右边孩子的key都大于它. 二叉树在查找和存储中通常能保持logn的查找.插入.删除,以及前驱.后继,最大值,最小值复杂度,并且不占用额外的空间. 这里演示二叉树的搜索及相关算法: #include<stack> #include<queue> using namespace std; class tree_node{ public

  • C语言实现的猴子吃桃问题算法解决方案

    本文实例讲述了C语言实现的猴子吃桃问题.分享给大家供大家参考,具体如下: 问题: 猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个.第二天又将剩下的桃子吃掉一半,又多吃了一个.以后每天都吃前一天剩下的一半零一个.到第10天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子? 解析: ① 从最后一天的x=1个,倒推出前一天的个数x,需要注意的是表达式为x=2(x+1),而不是x=2x+1,注意两者之间的区别,想清楚为什么第二种不正确. ② 将该表达式作为循环9次的循环体,并在该语

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • C语言经典算法例题求100-999之间的“水仙花数

    C语言经典算法例题求100-999之间的“水仙花数

    题目:打印出所有的 "水仙花数 ",所谓 "水仙花数 "是指一个三位数,其各位数字立方和等于该数本身. 例如:153是一个 "水仙花数 ",因为153=1的三次方+5的三次方+3的三次方. 实现代码如下 #include <iostream> #include <Cmath> using namespace std; /* 求100-999之间的水仙花数 */ int main() { int number,hun,ten

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

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

    本文实例讲述了C语言使用广度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 变量 head 和 tail 是队头和队尾指针, head 总是指向队头, tail 总是指向队尾的下一个元素.每个点的 predecessor 成员也是一个指针,指向它的前趋在 queue 数组中的位置.如下图所示: 广度优先是一种步步为营的策略,每次都从各个方向探索一步,将前线推进一步,图中的虚线就表示这个前线,队列中的元素总是由前线的点组成的,可见正是队列先进先出的性质使这个算法具有了广度优先的特点.广

  • C语言实现运筹学中的马氏决策算法实例

    本文实例讲述了C语言实现运筹学中的马氏决策算法.分享给大家供大家参考,具体如下: 一.概述 马氏决策(Markov decision)是马尔可夫决策过程(Markov Decision Processes,简记为MDP)的简称,是研究随机序贯决策问题的一门重要理论.马氏决策是一类可连续进行观察的随机动态系统的最优化决策,它将(确定性)动态规划与马尔可夫过程相结合,是随机离散事件动态系统惟一的动态控制方法. 关于马氏决策的具体说明可参考百度百科:https://baike.baidu.com/it

  • 基于C语言实现的aes256加密算法示例

    本文实例讲述了基于C语言实现的aes256加密算法.分享给大家供大家参考,具体如下: aes256.h: #ifndef uint8_t #define uint8_t unsigned char #endif #ifdef __cplusplus extern "C" { #endif typedef struct { uint8_t key[32]; uint8_t enckey[32]; uint8_t deckey[32]; } aes256_context; void aes

  • C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    C语言实现魔方阵算法(幻方阵 奇魔方 单偶魔方实现)

    例如三阶魔方阵为: 魔方阵有什么的规律呢? 魔方阵分为奇幻方和偶幻方.而偶幻方又分为是4的倍数(如4,8,12--)和不是4的倍数(如6,10,14--)两种.下面分别进行介绍. 2 奇魔方的算法 2.1 奇魔方的规律与算法 奇魔方(阶数n = 2 * m + 1,m =1,2,3--)规律如下: 数字1位于方阵中的第一行中间一列:数字a(1 < a  ≤ n2)所在行数比a-1行数少1,若a-1的行数为1,则a的行数为n:数字a(1 < a  ≤ n2)所在列数比a-1列数大1,若a-1的列

  • C语言实现的猴子分桃问题算法解决方案

    本文实例讲述了C语言实现的猴子分桃问题算法.分享给大家供大家参考,具体如下: 问题: 海滩上有一堆桃子,五只猴子来分.第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份.第二只猴子把剩下的桃子又平均 分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份,第三.第四.第五只猴子都是这样做的,问海滩上原来最少有多少个桃子? 程序: #include<stdio.h> int divided(int n, int m) //注意该递归函数的定义 { if(n/5

  • 基于C语言实现的迷宫算法示例

    本文实例讲述了基于C语言实现的迷宫算法.分享给大家供大家参考,具体如下: 利用c语言实现迷宫算法,环境是vc++6.0. #include<stdio.h> #include<time.h> #include<cstdlib> int visit(int,int); void setmaze(); int maze[11][11]= { {0,0,2,2,2,2,2,2,2,2}, {2,0,2,2,0,2,0,2,0,2}, {2,0,2,0,0,0,0,0,0,2}

  • 详解约瑟夫环问题及其相关的C语言算法实现

    约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

  • C语言实现斗地主的核心算法

    数据结构只选择了顺序表,没有选择链表,灵活性和抽象性不足,不能普适. head.h #ifndef __HEAD_H__ #define __HEAD_H__ #define MAXLEVEL 15 typedef struct CARD{ int number; int level; char *flower; char point; }card;//卡 typedef struct DECK{ int top; int arr[55]; }deck;//牌堆 typedef struct P

随机推荐