迷宫问题(一)-利用栈回溯

本题的前提:起点(1,1), 终点(8,8)

#include<stdio.h>
#include <stdlib.h>
#define OK      1
#define ERROR   0
#define TRUE    1
#define FALSE   0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
#define N 10

typedef int Status;
typedef char MazeType[N][N + 1];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

typedef struct {
  int x; //迷宫中的行
  int y; //迷宫中的列
} PosType; //坐标

typedef struct {
  PosType      seat;    //当前的坐标位置
  int   di;        //往下一个坐标位置的方向
} SElemType; //栈的元素类型

typedef struct {
  SElemType *base;
  SElemType *top;
  int stacksize;
} SqStack;

Status InitStack(SqStack &s)  //栈的初始化
{
  s.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));
  if(!s.base) exit(OVERFLOW);
  s.top = s.base;
  s.stacksize = STACK_INIT_SIZE;
  return OK;
}

Status Push(SqStack &s, SElemType e)
{
  if(s.top - s.base >= s.stacksize) { //栈满,追加存储空间
    s.base = (SElemType *)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));
    if(!s.base) exit(OVERFLOW);
    s.top = s.base + s.stacksize;
    s.stacksize += STACKINCREMENT;
  }
  *s.top++ = e;
  return OK;
}

Status Pop(SqStack &s, SElemType &e)
{
  if(s.top == s.base)return ERROR;
  e = * --s.top;
  return OK;
}

int StackEmpty(SqStack s)
{
  return s.base == s.top;
}

Status Pass(MazeType maze, PosType curpos) //判断当前节点是否通过
{
  return maze[curpos.x][curpos.y] == ‘ ‘ || maze[curpos.x][curpos.y] == ‘S‘
  || maze[curpos.x][curpos.y] == ‘E‘;
}

void FootPrint(MazeType &maze, PosType curpos) //留下足迹
{
  maze[curpos.x][curpos.y] = ‘*‘; //走过且走得通
}

PosType NextPos(PosType pos,int d){
    pos.x += dx[d];
    pos.y += dy[d];
    return pos;
}

void MarkPrint(MazeType &maze, PosType curpos) //留下不能通过的标记
{
  maze[curpos.x][curpos.y] = ‘!‘; //走过但走不通
}

//求解迷宫maze中,从入口start到出口end的一条路径
Status MazePath(MazeType &maze, PosType start, PosType end)
{
  SqStack s;
  SElemType e;
  InitStack(s);
  PosType curpos = start;
  do {
    if(Pass(maze, curpos)) { //如果当前位置可以通过,即是未曾走到的通道块
      FootPrint(maze, curpos);     //留下足迹
      if(curpos.x==end.x && curpos.y==end.y)
        return TRUE;
      e.seat = curpos;
      e.di = 0;
      Push(s, e);
      curpos = NextPos(curpos, 0);  //获得下一节点:当前位置的东邻
    }
    else { //当前位置不能通过
      if(!StackEmpty(s)) {
        Pop(s, e);
        while(e.di == 3 && !StackEmpty(s)) {
          MarkPrint(maze, e.seat);
          Pop(s, e);  //留下不能通过的标记,并退回一步
        }
        if(e.di < 3) {
          e.di++;
          Push(s, e);           //换一个方向探索
          curpos = NextPos(e.seat, e.di);   //设定当前位置是该方向上的相邻块
        }//if
      }//if
    }//else
  } while(!StackEmpty(s));
  return FALSE;
}
int main()
{
  int i;
  PosType start={1, 1}, end={8,8};
  MazeType maze;
  for(i = 0; i < 10; i++)
    gets(maze[i]);
  MazePath(maze, start, end);
  for(i = 0; i < 10; i++)
    puts(maze[i]);
  return 0;
}
时间: 06-11

迷宫问题(一)-利用栈回溯的相关文章

迷宫问题求解(一)利用栈与递归求解出口

本文适合于对迷宫问题已有初步研究,或阅读代码能力较强的人. 因此,如果你对迷宫问题一无所知,请参考其他更详细的资料. 迷宫问题,是一个对栈(Stack)典型应用的例子之一. 假如,有如下10X10的迷宫(0代表通路,1代表障碍),我们需要用写程序来找出迷宫的出口. 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0

栈回溯技术

转载于:http://blog.csdn.net/yangzhiloveyou/article/details/9042137 1.    前言 段错误.非法地址访问等问题导致程序崩溃的现象屡屡发生,如果能找到发生错误的函数,往往一眼就能看出BUG所在--对于这类比较简单的问题,比如使用空指针进行读写等,利用栈回溯技术可以很快定位.但是对于数组溢出.内存泄漏等问题导致的程序错误,往往隐藏很深,它们并不当场发作,即使我们一步一步跟踪到发生错误的语句时,也经常会让人觉得"这个地方根本不可能出错啊&q

数据结构应用:利用栈破解迷宫游戏

最近刚开始学数据结构,发现数据结构真是个神奇的东西哈,很多现实中的问题都可以用不同的数据结 构来解决,比如利用和栈中缀表达式编写一个计算机程序,利用栈破解迷宫游戏,今天我就来跟大家分 享一下如何利用栈来破解迷宫游戏. 学过数据结构的人都知道,栈的特点是:后进先出(First In Last Out);也就是说只能在栈的尾部进 行压栈和出栈,而且出栈的时候只能从最后一个数据开始.如下图: 而我们在破解迷宫游戏的时候采用的方法是"回溯",也就是在寻找通路的时候,每找到一个通路,就将这个数据

利用栈实现迷宫求解

利用栈实现迷宫求解 前言:众所周知,栈是(First in last out)先进后出的数据结构,利用这个属性可以实现类似与回溯的方式,比如当前数据满足条件,则入栈,否则出栈返回上一级,依次循环. 在本题中,将每个迷宫路径上的点封装成上下左右四个方向数节点,先入栈迷宫入口节点,如果上下左右没被使用,则将其上下左右的点入栈,否则出栈.如果最终达到迷宫终点则成功,否则失败. 如下是每个节点的数据结构 1 typedef struct{ 2 int top; 3 int bottom; 4 int l

利用栈求解迷宫问题

利用栈求解迷宫问题 源代码: #include<stdio.h> #include<stdlib.h> #define M 8 #define N 8 #define MaxSize M*N typedef struct { int i;//当前方块的行号 int j;//当前方块的列号 int di; //di是下一个可走的相邻方块的方位号 }Box; typedef struct { Box data[MaxSize]; int top;      //栈顶指针 }StType

利用栈计算算数表达式的值

先将中缀表达式利用栈转换为后缀表达式,然后再利用栈由后缀表达式计算算数表达式的值,具体代码如下: #include <iostream> using namespace std; #include <string> #include <vector> #include <stack> enum Type { OP_NUM, OP_SYMBOL, }; enum Operat { ADD, SUB, MUL, DIV, }; struct Cell { Typ

zoj1004-Anagrams by Stack 【栈 回溯】

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4 Anagrams by Stack Time Limit: 2 Seconds      Memory Limit: 65536 KB How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert

利用栈逆序元素

要求:利用栈将数组的元素逆序输出 分析:        1.数组中的元素是线性排列 2.栈的特点是先进后出 解题思路:将数组中的元素依次压栈,再出栈.就能实现对数组元素的逆序 1.定义结构体 #define N 50 struct mystack { int top; //栈顶元素 int data[N]; }; struct mystack selfStack={-1,{0}}; //初始栈为空 2.声明函数 int isEmpty();//判断栈是否为空 返回值:1-->空 0-->非空

将中缀表达式转换为后缀表达式,然后利用栈对表达式求值。

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <script src="js.js"></script> </head> <body> 输入中缀表达式空格分隔 例如 2 + 3 <input type=