迷宫问题代码算法详解

*问题描述：一个网格迷宫由n行m列的单元格组成，每个单元格要么是空地（用1表示）， * 要么是障碍物(用0 表示)。找出从起点到终点的最短移动序列，其中U,D,L,R, * 分别代表往上，下，左，右移动到相邻单元格。任何时候都不能在障碍格中， * 也不能走到迷宫之外，起点和终点保证是空地。n,m<=100. * *分析： 可以使用bfs，节点的访问顺序恰好是它们从根节点距离从小到大的顺序。类 * 似的，也可以用bfs来按照起点的距离顺序遍历迷宫图。不断沿着父亲指针走， * 保存方向序列dir，最后反向输出。 * 比深度优化的效率要高很多，因为每次都定义了活结点还有下一个扩展节点， * 在活结点当中去寻找扩展节点，不会盲目的搜索到底，而是有一定的选择性。 * 因此我们可以定义记录扩展节点的数组，并且定义函数来判断，看下一层将要 * 被搜索的节点是不是能够作为扩展节点。这就运用到了分支限界的知识。 *

/******************************************************************************
                          分支限界--走迷宫问题 
*******************************************************************************/
/*
*问题描述：一个网格迷宫由n行m列的单元格组成，每个单元格要么是空地（用1表示），
*          要么是障碍物（用0 表示）。找出从起点到终点的最短移动序列，其中UDLR
*          分别代表往上，下，左，右移动到相邻单元格。任何时候都不能在障碍格中，
*          也不能走到迷宫之外，起点和终点保证是空地。nm<=100.
* 
*分析：    可以使用bfs，节点的访问顺序恰好是它们从根节点距离从小到大的顺序。类
*          似的，也可以用bfs来按照起点的距离顺序遍历迷宫图。不断沿着父亲指针走，
*          保存方向序列dir，最后反向输出。
*          比深度优化的效率要高很多，因为每次都定义了活结点还有下一个扩展节点，
*          在活结点当中去寻找扩展节点，不会盲目的搜索到底，而是有一定的选择性。 
*          因此我们可以定义记录扩展节点的数组，并且定义函数来判断，看下一层将要
*          被搜索的节点是不是能够作为扩展节点。这就运用到了分支限界的知识。
* 
*/

#include
#include
using namespace std;

#define MAXN 1000
//int dir[MAXN];     //非递归显示该迷宫遍历格子的时候需要使用的寄存数组。 
int q[MAXN*MAXN];    //该数组表示存放选入成为活结点的，节点的编号

int n = 6m = 5;     //定义一个具有六行五列的格子阵。n是表示行数量，m表示列数量 

int dx[4]={-1100};//行列变换数组，定义下标0123，分别代表上下左右，
                     //dx代表行号通过上下左右进行的变换， 因此dx[0]=-1表示向上
                     //移动行号变为-1，dx[1]=1表示向下移动行号+1，
                     //表示dx[2]=0dx[3]=0 左右行号不变 
                     
int dy[4]={00-11};//定义下标0123，分别代表上下左右，
                     //因此在上下的时候列号不变，左右的时候列号-1，+1. 
                     
int fa[6][5];       // 保存新格子的父亲编号。 
int last_dir[6][5]; //记录上下左右的数组，其数值只能为0123 。存放的是之前的
                    //格子到当前格子所需要前进的方向。0123，分别代表上下左右 
                    
int dist[6][5];     //保存，扩展到该节点所用的步数 

int vis[6][5];      //只存两个数0和1。并且1表示格子满0表示格子空 
 
char name[10];      //打印移动方向的时候所对应的方向名字。 
 

void bfs（int x int y）
{
     int front = 0  rear = 0  du;
     
     u=x*m+y;          //x表示行号，y表示列号u表示编号。
     vis[x][y]=1;      //vis记录格子（xy）是否被走过。1表示格子满，0表示格子空。
     fa[x][y] = u;     //保存新格子的父亲编号，以便打印的时候遍历所有的格子。 
     dist[x][y]=0;     //保存，起点扩展到该节点所用的步数为0 
     q[rear++] = u ;   //存放活节点对应的编号。
      
     while（front < rear）//当数组最后一个元素的四个方向都无法扩展之后，
                        //及rear=front的时候退出循环 
     {
       u=q[front++];    //取出活结点当中的首元素作为扩展节点， 
       x = u/m; y = u%m;
       for（d=0;d<4;d++） //遍历四个方向 
       {
          int nx = x + dx[d]ny = y+dy[d];//算出新的行坐标与列坐标 
          
          if（nx>=0&&nx=0&&ny          {
            int v = nx*m+ny;             //算出新的数字编号 
            q[rear++] = v;               //将该活节点的编号放入到活结点的队列里。 
            vi