迷宫求解

算法

本文主要来源《啊哈!算法》第4章第2、3节

需要解决的问题

一个迷宫，由n行m列的单元格组成(0 < n,m <= 50)，每个空格要么为障碍物，要么为空格，求一条从迷宫起点(1,1)到目标地点(小哈的位置)的最短路径。

分析

深搜

规定一个搜索顺序（右下左上），一直走下去。如果没有到达，继续枚举四个方向搜索；如果超过迷宫边界还没到达，则该次递归结束；如果到达小哈的位置，则停止改点的下次搜索，这时候比较最小值，存下来。最后输出最小值。

广搜

通过起点去向下一个位置探索，将下一步可以到达的位置加入队列，并标记已经走过。然后从队列中依次取点，再向下一步可以到达的位置探索，再加入队列，直到到达小哈的位置为止。

代码

dfs

//
//  main.cpp
//  Maze_dfs
//
//  Created by jtusta on 2017/6/19.
//  Copyright © 2017年 jtahstu. All rights reserved.
//

#include <iostream>
#include <cstdio>

using namespace std;

int n,m,p,q,minx=999999;
int a[51][51],book[51][51];

void dfs(int x,int y,int step){
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    int tx,ty,k;
    if(x==p && y==q){   //判断是否到达小哈的位置
        if(step<minx)
            minx=step;
        return;
    }
    
    for(k=0;k<4;k++){   //向四个方向枚举
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<1 || tx>n || ty<1 || ty>m)    //判断是否越界
            continue;
        if(a[tx][ty]==0 && book[tx][ty]==0){
            book[tx][ty]=1;     //标记这个点已经走过
            dfs(tx,ty,step+1);      //开始尝试下一个点
            book[tx][ty]=0;     //尝试结束，取消这个点标记
        }
    }
    return;
}

int main() {
    int i,j,startx,starty;
    cin>>n>>m;      //n行m列的迷宫
    for(i=1;i<=n;i++)       //读入迷宫
        for(j=1;j<=m;j++)
            cin>>a[i][j];
    cin>>startx>>starty>>p>>q;
    
    book[startx][starty]=1;     //标记起点，防止后面重复走==
    dfs(startx,starty,0);
    cout<<minx<<endl;       //
    return 0;
}
/*
 * 测试数据
 5 4
 0 0 1 0
 0 0 0 0
 0 0 1 0
 0 1 0 0
 0 0 0 1
 1 1 4 3
 */

 5 4
 0 0 1 0
 0 0 0 0
 0 0 1 0
 0 1 0 0
 0 0 0 1
 1 1 4 3
7
Program ended with exit code: 0

bfs

//
//  main.cpp
//  Maze_bfs
//
//  Created by jtusta on 2017/6/19.
//  Copyright © 2017年 jtahstu. All rights reserved.
//

#include <iostream>
#include <cstdio>

using namespace std;

struct note
{
    int x,y,f,s;    //横纵坐标、父亲在队列中的编号、步数
    //父亲在队列中的编号，本体不要求输出路径，可以不需要f
};

int main() {
    struct note que[2501];
    int a[51][51]={0},book[51][51]={0};
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};     //向四个方向走的数组
    int head,tail;
    int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
    
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            cin>>a[i][j];
    cin>>startx>>starty>>p>>q;
    
    head=1;     //队列初始化
    tail=1;
    que[tail].x=startx;     //往队列插入迷宫入口坐标
    que[tail].y=starty;
    que[tail].f=0;
    que[tail].s=0;
    tail++;
    book[startx][starty]=1;
    
    flag=0;
    while(head<tail){
        for(k=0;k<4;k++){       //枚举四个方向
            tx=que[head].x+next[k][0];
            ty=que[head].y+next[k][1];
            if(tx<1 || tx>n || ty<0 || ty>m)    //是否越界
                continue;
            //判断是否为障碍物 或者已经在路径中
            if(a[tx][ty]==0 && book[tx][ty]==0){
                book[tx][ty]=1;     //把这个点标记为走过，注意宽搜每个点只入列一次，所以和深搜不同，不需要将book数组还原
                //插入新的点到队列中
                que[tail].x=tx;
                que[tail].y=ty;
                que[tail].f=head;       //因为这个点是从head拓展而来，所以它的父亲是head，本题目不需要求路径，因此本句可以省略
                que[tail].s=que[head].s+1;
                tail++;
            }
            if(tx==p&&ty==q){
                flag=1;
                break;
            }
        }
        if(flag==1)
            break;
        head++;     //此地方不能忘记，当一个点拓展结束，head++才能对后面的点再进行拓展
    }
    //打印队列中末尾最后一个点（目标点）的步数
    //注意tail是指向队列队尾（即最后一位）的下一个位置，所以这需要-1
    cout<<que[tail-1].s<<endl;
    
    return 0;
}
/*
 测试数据
 5 4
 0 0 1 0
 0 0 0 0
 0 0 1 0
 0 1 0 0
 0 0 0 1
 1 1 4 3
 */

 5 4
 0 0 1 0
 0 0 0 0
 0 0 1 0
 0 1 0 0
 0 0 0 1
 1 1 4 3
7
Program ended with exit code: 0

---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可，转载必须注明作者和本文链接。

---