C++迷宫问题的求解算法分享！

本文实例为大家分享了C++实现迷宫的具体代码，供大家参考，具体内容如下

一、 实验目的：

（1） 熟练掌握链栈的基本操作及应用。
（2） 利用链表作为栈的存储结构，设计实现一个求解迷宫的非递归程序。

二、实验内容：

【问题描述】

以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对信任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【基本要求】

首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），……。

【测试数据】/strong>

迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。
1   2   3   4   5   6   7   8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0

【实现提示】

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通睡。
可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。

【选作内容】

（１） 编写递归形式的算法，求得迷宫中所有可能的通路；
（２） 以方阵形式输出迷宫及其通路。

网友提供了一段解决算法：

  #include<stdio.h>  #include<stdlib.h>    #define m 4//行    #define n 4//列      struct xy  {    int x;    int y;  };  typedef struct stack  {    struct xy coordinate;    struct stack* next;  }stack;    void init(stack* p)  {        p->next = NULL;  }    void push(stack* p,struct xy cdnt)  {    stack* temp = p;    while(temp->next != NULL)      temp = temp->next;    stack* newValue = (stack*)malloc(sizeof(struct stack)*1);    newValue->coordinate = cdnt;    newValue->next = temp->next;    temp->next = newValue;  }    void pop(stack* p)  {    stack* tempp = p;    stack* temp = p->next;    while(temp->next != NULL)      temp = temp->next,tempp = tempp->next;    tempp->next = NULL;    free(temp);  }    void browse(stack* p)  {    stack* temp = p->next;    while(temp != NULL)      printf("(%d,%d)n",temp->coordinate.y,temp->coordinate.x),temp = temp->next;  }    struct xy getEnd(struct stack* p)  {    stack* temp = p;    while(temp->next != NULL)      temp = temp->next;    return temp->coordinate;  }    int getSize(stack* p)  {    int size = 0;    stack* temp = p->next;    while(temp != NULL)    {      size++;      temp = temp->next;    }    return size;  }  int main()  {      int path[m+1][n+1] = {0};    int col = 0,row = 0;    int i = 0,j = 0;    int temp_col = 0,temp_row = 0,t_col = 0,t_row = 0;    int flag = 0;    struct xy t_pair;    //stack A,B;      stack* Ahead = (stack*)malloc(sizeof(struct stack)*1);    stack* Bhead = (stack*)malloc(sizeof(struct stack)*1);    init(Ahead); init(Bhead);      for(;i<m;i++)      for(j=0;j<n;j++)        {          printf("input 0 or 1n");          scanf("%d",&path[i][j]);        }    i = j = 0;      if(path[0][0] == 0 || path[m-1][n-1] == 0)    {      printf("There is no wayn");      return 1;    }    while(1)    {      //检验是否已经到达末尾        if(col == n-1 && row == m-1 && path[row][col] == 1)      {        //到达尾端，意味着找到一条路          flag = 1;        printf("Find a way,it'sn");        browse(Ahead);        printf("(%d,%d)n",m-1,n-1);        if(getSize(Bhead) != 0)        {                    temp_col = getEnd(Bhead).x;          temp_row = getEnd(Bhead).y;            while(1)            if(getEnd(Ahead).x == temp_col && getEnd(Ahead).y == temp_row)              break;            else              pop(Ahead);          col = temp_col + 1;          row = temp_row;          pop(Bhead);          }        else          return 1;       }        else//还没有到末尾的情况        {         if(path[row + 1][col] == 1 && path[row][col + 1] == 1)        {          t_pair.x = col;t_pair.y = row;          push(Ahead,t_pair);          push(Bhead,t_pair);          row++;          continue;        }        //下面不是右边也不是          if(path[row + 1][col] == 0 && path[row][col + 1] == 0)        {          if(getSize(Bhead))          {            //vector<struct xy>::iterator iter = B.end() - 1;              col = getEnd(Bhead).x + 1;row = getEnd(Bhead).y;//回到上一次分叉处，搜索右侧路径              pop(Ahead);            pop(Bhead);            continue;          }          else            return 1;        }        //下面是，右边不是          if(path[row + 1][col] == 1 && path[row][col + 1] == 0)        {          t_pair.x = col;t_pair.y = row;          push(Ahead,t_pair);          row++;          continue;        }        //下面不是，右边是          if(path[row + 1][col] == 0 && path[row][col + 1] == 1)        {          t_pair.x = col;t_pair.y = row;          push(Ahead,t_pair);          col++;          continue;        }                }    }    if(!flag)      printf("There is no wayn");    return 0;  }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。

—-想了解C++迷宫问题的求解算法分享！全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>