迷宫问题的求解思路

     一个网格迷宫由n行m列的单元格组成，每个大院个要么是空地（用1表示），要么是障碍物（用0表示）。你的任务是找一条从起点到终点的最短移动序列，其中UDLR分别表示往上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中，也不能走到迷宫之外。起点和终点保证是空地。n,m<100。

 

的求解方法

 

 

其具体dfs代码为：

int q[MAXN]; 
void bfs(int x,int y)//给的参数是点
{
    int front=0,rear=0,d,u;
    u=x*m+y;     //把点化为坐标存储在m*n的表格中
    vis[x][y]=1; //把点（x,y）置为已经访问     
    fa[x][y]=u;  //把化为编号的号码放在fa数组中存放
    dist[x][y]=0;该数组中存放深度遍历时的遍历号码
    q[rear]=u;  //把编号放在q数组中
    while(front    {
        u=q[front++];  
        x=u/m;
        y=u%m;
        for(d=0;d<4;d++)//这是4个方向的遍历
        {
            int nx=x+dx[d],ny=y+dy[d]; //取到下一个方向
//深度遍历的点的坐标
            if(nx>=0&&nx=0&&ny<=m&&maze[nx][ny]&&!vis[nx][ny])
                {//判断有没有越界 已经被访问 或者是不是不能访问
                    int v=nx*m+ny;//通过新的坐标生成新的编号
                    q[rear++]=v;
                    vis[nx][ny]=1;
                    fa[nx][ny]=u;//存放坐标化为的编码
                    dist[nx][ny]=u;//记下深度遍历时的序号
                    last_dir[nx][ny]=d;//用来保存方向
                }
        }
    }

}

 

 

 

 

这个图表述的是从第一个点扩展开始的顺序和父亲指针

                    这是dist二维数组来盛放的从各个左上角 开始 到达各个格子的最短距离

 

 

fa[][]这个二维数组用来盛放父亲节点的节点序列

这个程序避免了结构体的困扰

而换做  把格子从0开始从上到下编号到-----n*m ，因此i行第j个格子的编号为i*m+j，而编号为u的行号为u/m，列号为u%m，当格子（x，y）扩展到（nx，ny）后，我们要更新的有

dist[nx][ny]=dist[x][y]+1

还有保存新格子（nx，ny）的父亲编号fa[nx][ny]以及

到这个父亲节点的方向last_dir[nx][ny]

 

 

具体代码如下：

这是一个5*5的缩写

#include

#include<iostream>
#include<queue>
#include<vector>

usingnamespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int maze[5][5];//数据输入地图
int vis[5][5];//记录是否访问过
int dist[5][5];//记录每一个点到起点的最近距离
void bfs(int x,int y){
    queue<int>q;//BFS搜索用队列实现
    int d,u=0;
    vis[x][y]=1; q.push(u); while(q.size()!=0){
        u=q.front();//u和下面的临时变量v的作用是将二维图转化为一维数列存储
                   //该方法可以避开另建立结构体记录横坐标值和纵坐标值
                   //例如u=20即代表着第四行（从零算起）第零列的位置
                   //其中转化方法为下面两句
        q.pop();//从队头拿出一个数
        x=u/5; //除以列数，及得到第几行
        y=u%5; //对列数取模，记得到列数
        for(int i=0;i<4;i++){//上下左右查找
            int nx = x+dir[i][0],
                ny = y+dir[i][1];
            if(nx>=0&&nx<=4&&ny>=0&&ny<=4&&!maze[nx][ny]&&!vis[nx][ny]){
                int v = nx*5+ny;
                q.push(v);//加入队尾
                vis[nx][ny]=1;
                dist[nx][ny]=dist[x][y]+1;
            }
        }
    }
}
//得到最近矩阵列后，再从终点到起始查找输出
void print(){
    vector<int>arr;
    arr.push_back(24);
    int location=24;
    int temp=dist[4][4]-1;
    while(temp>=0){
        int x=location/5,
            y=location%5;
        int nx,ny;
        for(int i=0;i<4;i++){
                nx=x+dir[i][0],
                ny=y+dir[i][1];
            if(nx>=0&&nx<=4&&ny>=0&&ny<=4&&dist[nx][ny]==temp)
                break;
        }
        location=nx*5+ny;
        arr.push_back(location);
        temp--;//题目说有唯一解，那么如果右下角的数值为8，那么路径必须在dist矩阵中是
              //7,6,5,4....1,0，以此可以找到路径。
    }
    cout<<"(0, 0)"<<endl;
    for(int i=arr.size()-2;i>=0;i--){
        cout<<"("<<arr[i]/5<<", "<<arr[i]%5<<")"<<endl;
    }
}


int main(){
    int i,j;
    memset(vis,0,sizeof(vis));
    memset(dist,0,sizeof(dist));
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
            cin>>maze[i][j];
    bfs(0,0);
   //输出dist矩阵检验输出
   //因为dist矩阵是print()的基础
/* for(i=0;i<5;i++){
        for(j=0;j<5;j++)cout<<dist[i][j]<<" ";
        cout<<endl;
    }
*/
    print();
    return0;
}
//测试数据
/*
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