[图]BFS应用之迷宫问题

一般迷宫类问题（求最短路径）均可用BFS求解

1. 网易 地牢逃脱

给定一个 n 行 m 列的地牢，其中 ‘.’ 表示可以通行的位置，’X’ 表示不可通行的障碍，牛牛从(x0,y0)(x0,y0) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 ‘.’。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0x0< n, 0 <= y0y0< m，左上角的坐标为 （0, 0），出发位置一定是 ‘.’）。之后的一行包含一个整数 k（0 < k<= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）
输出描述:

输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。
输入例子:
3 3
...
...
...
0 1
4
1 0
0 1
-1 0
0 -1

输出例子:
3

讲解：

题意：
题目中说“最坏情况下，他需要多少步才可以离开这个地牢。” 是指， 在给定地牢的形状后，出口允许设置在任意一个“.”所在的位置，主人公在知道了出口点后，会试图以最短的路径走向出口，现在需要求，如果把出口设在了一个最难以到达的位置， 需要多少步才能到达出口点。

思路：
一般迷宫问题都可以用BFS解决，本题属于迷宫问题，首先考虑BFS.
BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
在本题中，如果地牢中所有“.”点都被访问了，说明主人公可以访问任意一个节点，也就是说无论出口放在哪里，主人公都可以出地牢。

#include<iostream>
#include<cstdlib>
#include<queue>
using namespace std;

struct Node{
    int x;
    int y;
    int step;//从出发点到该节点的步数
};

int n,m;//地牢规模
char map[50][50];//地牢
int startX,startY;//出发点
int moveNum;//主人公可以行走的方式数
int moveTypes[50][2];//行走方式
queue<Node> q_node;

int BFS()
{
    int maxSteps = 0;
    int outX = -1;
    int outY = -1;
    while (!q_node.empty())
    {
        Node node_out = q_node.front();
        q_node.pop();
        maxSteps = max(maxSteps,node_out.step);//选择按照不同行走方式中步数最大的点。
        outX = node_out.x;
        outY = node_out.y;
        for(int i = 0; i < moveNum; i++)//按照不同行走方式计算可达的点
        {
            int nextX = node_out.x + moveTypes[i][0];
            int nextY = node_out.y + moveTypes[i][1];
            
            if(nextX>=0 && nextX<n && nextY>=0 &&nextY<m && map[nextX][nextY]!='X')
            {
                Node node_in;
                node_in.x = nextX;
                node_in.y = nextY;
                map[nextX][nextY] = 'X';//每访问一个点，将这个点设置为已经访问
                node_in.step = node_out.step+1;
                q_node.push(node_in);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(map[i][j] == '.')//如果地牢中还存在“.”表明：如果出口选在该点处，主人公出不了地牢
            {
                return -1;
            }

        }
    }

    return maxSteps;

}

int main()
{
    //freopen("in.txt","r",stdin);
    
    cin>>n>>m;

    
    for(int i = 0; i < n; i++)
    {

        for (int j = 0; j < m; ++j)
        {
            cin>>map[i][j];
        }
    }

    
    cin>>startX;
    cin>>startY;

    
    cin>>moveNum;

    
    for (int i = 0; i < moveNum; ++i)
    {
        for(int j = 0; j < 2; j++)
        {
            cin>>moveTypes[i][j];
        }
    }
    
    Node node;
    node.x = startX;
    node.y = startY;
    map[startX][startY] = 'X';

    
    q_node.push(node);

    
    int maxStep = BFS();

    cout<<maxStep;

    return 0;
}

2. 打印出迷宫的最短路径和所有路径

给定迷宫，以及迷宫的入口点和出口点，求从入口点到出口点的最短路径和所有的路径

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <stack>
#include <queue>

using namespace std;

typedef struct point{
    int x;
    int y;
    point *previous;
    int step;
} point;

point dir[4] = {
    { 0, 1, NULL, 0 },
    { 1, 0, NULL, 0 },
    { 0, -1, NULL, 0 },
    { -1, 0, NULL, 0 },
};

//只有0位置可以走，到数组边缘就是走出迷宫。
//输出最短的路径和最短步数
int map[8][8] = {
    { 1, 0, 1, 1, 1, 1, 1, 1 },
    { 1, 0, 0, 0, 0, 0, 0, 1 },
    { 1, 0, 1, 1, 1, 1, 0, 1 },
    { 1, 0, 0, 0, 0, 1, 0, 0 },
    { 1, 1, 1, 1, 0, 0, 1, 1 },
    { 1, 1, 1, 1, 1, 0, 1, 1 },
    { 1, 1, 0, 0, 0, 0, 1, 1 },
    { 1, 1, 0, 1, 1, 1, 1, 1 },
};

void PrintAllPath(point *p)
{
    int shortest = p->step;
    
    cout << "可行短路径为：";
    while (p->previous != NULL)
    {
        cout << "(" << p->x << "," << p->y << ")";
        p = p->previous;
    }
    cout << "(" << p->x << "," << p->y << ")" << endl;
    cout << "路径长度为：" << shortest << endl;
}

void BFS(point startPoint)
{
    queue<point> q;
    q.push(startPoint);
    point cur;

    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        map[cur.x][cur.y] = 1;

        for (int i = 0; i < 4; i++)
        {
            point nxt{ cur.x + dir[i].x, cur.y + dir[i].y, NULL, 0 };
            if (nxt.x >= 0 && nxt.x < 8 && nxt.y >= 0 && nxt.y < 8 && map[nxt.x][nxt.y] == 0)
            {
                point *tmp = new point;
                memcpy(tmp, &cur, sizeof(point));
                nxt.previous = tmp;
                nxt.step = cur.step + 1;
                map[nxt.x][nxt.y] = 1;

                if (nxt.x == 0 || nxt.x == 7 || nxt.y == 0 || nxt.y == 7)
                {
                    PrintAllPath(&nxt);//第一个到达该点的路径即为最短路径

                    //这句话注释则输出所有路径，不注释是最短路径
                    //return;
                }
                q.push(nxt);
            }
        }
    }
}

int main()
{
    point startPoint{ 0, 1, NULL, 0 };
    BFS(startPoint);

    return 0;
}

总结：
在设计点坐标时，需要几个参量：

• 本节点x，y；如果发现本节点合法，则需要将上一节点复制一份，将其作为本节点的前驱。
• 上一个节点x，y；
• 已经走的步数。

配合这个左边点数据结构不断进入队列，当此节点碰到边界时则走出去，函数返回则是最短路径。
不return，则会输出所有的路径和步数。