数据结构中迷宫问题求解

简介: 数据结构中迷宫问题求解

迷宫问题求解

问题描述:

给定一个迷宫从入口到出口的路径,具体要求如下:

1.迷宫以16*16的矩阵存储在本地文件中,格式自定义。

2.迷宫障碍占一定的比列,

3.非递归形式求解问题

4.汇出迷宫路径(以命令行或者GUI)

5.无路可走时,请给出提示

本节是数据结构中运用栈思想去求解迷宫问题,本算法实现简单,代码仅供参考,如有疑问请评论联系:
#include <stdio.h>
#include <stdlib.h>
#define COUNT_I 17
#define COUNT_J 17
#define START_I 0
#define START_J 0
#define END_I 15
#define END_J 15
#define MAXSIZE 1000
//坐标位置结构体
typedef struct local{
  int x;
  int y;
}LOCAL;
//栈结构
typedef struct stack{
  LOCAL data[MAXSIZE];
  int top;
  int base;
}STACK;
//初始化栈
STACK *InitStack(void)
{
  STACK *maze;
  maze = (STACK *)malloc(sizeof(STACK));
  maze->top = maze->base=-1;
  return maze;
}
//判栈空
int EmptyStack(STACK *maze)
{
  if (maze->top ==maze->base)
    return 1;
  else
    return 0;
}
//判栈满
int IsFull(STACK *maze)
{
  if (maze->top-maze->base== MAXSIZE)
    return 1;
  else
    return 0;
}
//入栈
int PushStack(STACK *maze, LOCAL *x)
{
  if (maze->top <= MAXSIZE - 1){
    maze->data[++maze->top] = *x;
    return 1;
  }
  else{
    printf("栈已满\n");
    return 0;
  }
}
//出栈
int PopStack(STACK *maze, LOCAL *x)
{
  if (maze->top >maze->base){
    *x = maze->data[maze->top];
    maze->top--;
    return 1;
  }
  else{
    printf("栈已空\n");
    return 0;
  }
}
//走迷宫函数
int VistMaze(int maze[][COUNT_J], LOCAL path[][COUNT_J])
{
  int i, j;
  //初始化栈
  STACK *stack;
  LOCAL temp;
  stack = InitStack();
  temp.x = 0; temp.y = 0;
  if (maze[START_I][START_J] == 0)
    PushStack(stack, &temp);
  else
    return 0;
  while(!EmptyStack(stack)){
    PopStack(stack, &temp);
    i = temp.x; j = temp.y;
    maze[i][j] = 2;
    if (i == END_I && j == END_J)
      break;
    //下
    if (i + 1 <= END_I && maze[i + 1][j] == 0){
      maze[i + 1][j] = 2;
      path[i + 1][j].x = i;
            path[i + 1][j].y = j;
      temp.x = i + 1;
      temp.y = j;
      PushStack(stack, &temp);
    }
    //右
    if (j + 1 <= END_J && maze[i][j + 1] == 0){
      maze[i][j + 1] = 2;
      path[i][j + 1].x = i; path[i][j + 1].y = j;
      temp.x = i;
      temp.y = j + 1;
      PushStack(stack, &temp);
    }
    //左
    if (j - 1 >= 0 && maze[i][j - 1] == 0){
      maze[i][j - 1] = 2;
      path[i][j - 1].x = i; path[i][j - 1].y = j;
      temp.x = i;
      temp.y = j - 1;
      PushStack(stack, &temp);
    }
    //上
    if (i - 1 >= 0 && maze[i - 1][j] == 0){
      maze[i - 1][j] = 2;
      path[i - 1][j].x = i; path[i - 1][j].y = j;
      temp.x = i - 1;
      temp.y = j;
      PushStack(stack, &temp);
    }
  }
  //如果到达终点而退出的循环则将路径标识出来
  if (i == END_I && j == END_J){
    maze[i][j] = 3;
    while(path[temp.x][temp.y].x != -1){
      temp = path[temp.x][temp.y];
      maze[temp.x][temp.y] = 3;
    }
    return 1;
  }
  else{
    return 0;
  }
}
int main(void)
{
  //迷宫
  int i, j;
  FILE *fp;
  int maze[COUNT_I][COUNT_J] ;
    fp=fopen("keshedemo.txt","r");
    if(!fp)
        printf("文件错误");
    for(i=0;i<=16;i++)
    {
        for(j=0;j<=16;j++)
        {
            printf('da');
            fscanf(fp,"%3d",&maze[i][j]);
        }
    }
    fclose(fp);
    fp=0;
/*        for (i=0;i<=16;i++)
        {
            for(j=0;j<=16;j++)
                fprintf(fp,"%3d",maze[i][j]);
            fprintf(fp,"\n");
        }
        fclose(fp);
 */
  //定义路径数组,将到(x,y)点的路径保存进数组
  LOCAL path[COUNT_I][COUNT_J];
  for(i = 0; i < COUNT_I; i++){
    for(j = 0; j < COUNT_J; j++){
      path[i][j].x = -1;
      path[i][j].y = -1;
    }
  }
  //打印出迷宫
  printf("原迷宫:\n");
  for(i = 0; i <= COUNT_I; i++)
    printf("-");
  printf("\n");
  for (i = 0; i < COUNT_I; i++){
    printf("|");
    for (j = 0; j < COUNT_J; j++){
      if (maze[i][j] == 1)
        printf("*");
      else
        printf(" ");
    }
    printf("|\n");
  }
  for(i = 0; i <= COUNT_I; i++)
    printf("-");
  printf("\n");
  if (VistMaze(maze, path) == 0){
    printf("没有路径可走\n");
    exit(0);
  }
  //打印出迷宫和路径
  printf("迷宫和路径:\n");
  for(i = 0; i <= COUNT_I; i++)
    printf("-");
  printf("\n");
  for (i = 0; i < COUNT_I; i++){
    printf("|");
    for (j = 0; j < COUNT_J; j++){
      if (maze[i][j] == 1)
        printf("*");
      else if (maze[i][j] == 3)
        printf("0");
      else
        printf(" ");
    }
    printf("|\n");
  }
  for(i = 0; i <= COUNT_I; i++)
    printf("-");
  printf("\n");
  return 0;
}
相关文章
|
12月前
|
存储 算法 编译器
【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列
【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列
83 0
|
20天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
29 0
|
5月前
|
算法
数据结构与算法-DFS+BFS篇(迷宫问题)
数据结构与算法-DFS+BFS篇(迷宫问题)
59 3
数据结构实验之图论四:迷宫探索
数据结构实验之图论四:迷宫探索
|
算法 定位技术 C语言
【数据结构】迷宫问题DFS非递归(c语言实现)
【数据结构】迷宫问题DFS非递归(c语言实现)
116 0
|
测试技术
数据结构中【迷宫问题】的两个OJ题2
今天是美好的一天,现在是体育课时间,我神奇的体育老师让我们男生需要做40个俯卧撑作为期末作业,可惜啊可惜,我差了一丝丝,这个东西对于我这种高瘦子还是有很大的挑战的,我现在能充分的感觉到码字的手已经不是那么的正常了,本人是热爱运动的,但是对于引体向上和俯卧撑这种运动我从事感到无可奈何,难!难!难!所以各位同学一定要加强锻炼哦!今天的这篇博客是比较特殊的一次,因为现在是北京时间:2022/12/30/17:06 ,可以看出现在不是凌晨,本来确实是想在凌晨的时候将这篇博客给产出的,但是怕因为困而影响了质量,所以我留到了现在来写。ok!我们现在就开始学习一下有关数据结构中的迷宫问题,我们从初阶的迷宫问
|
算法 测试技术 编译器
数据结构中【迷宫问题】的两个OJ题1
今天是美好的一天,现在是体育课时间,我神奇的体育老师让我们男生需要做40个俯卧撑作为期末作业,可惜啊可惜,我差了一丝丝,这个东西对于我这种高瘦子还是有很大的挑战的,我现在能充分的感觉到码字的手已经不是那么的正常了,本人是热爱运动的,但是对于引体向上和俯卧撑这种运动我从事感到无可奈何,难!难!难!所以各位同学一定要加强锻炼哦!今天的这篇博客是比较特殊的一次,因为现在是北京时间:2022/12/30/17:06 ,可以看出现在不是凌晨,本来确实是想在凌晨的时候将这篇博客给产出的,但是怕因为困而影响了质量,所以我留到了现在来写。ok!我们现在就开始学习一下有关数据结构中的迷宫问题,我们从初阶的迷宫问
|
算法 数据可视化 编译器
数据结构 | 迷宫问题【栈与队列的交际舞】
通过栈与队列两种数据结构去实现迷宫问题路径得求解,人生真的在走迷宫吗?
184 0
数据结构 | 迷宫问题【栈与队列的交际舞】
|
Java
数据结构,Java实现递归回溯,寻找出迷宫路线,解决迷宫问题
数据结构,Java实现递归回溯,寻找出迷宫路线,解决迷宫问题
84 0
数据结构,Java实现递归回溯,寻找出迷宫路线,解决迷宫问题
|
算法 定位技术 开发者
数据结构和算法—迷宫回溯问题(2)|学习笔记
快速学习数据结构和算法—迷宫回溯问题(2)