迷宫问题

一，无权值迷宫

如下图所示的一个迷宫，

其中1表示障碍，求从左上角出发到各个点的最短距离
这时很容易想到的就是广度优先搜索
可以借助队列实现
首先（0，0）入队列
为了方便理解，下面会给出两个图，左图为最小步数，右图为队列的顺序

当队列不为空时，执行以下操作
获得队首（0，0）并出队列,并把临近的点（1，0）进队列，并得出到该点的步数，如图：

接着获得队首（1，0）并出队列，把临近的点（2，0）进队列，如图：

接下来很多是相同的，
上面的处理基本上是一次只进一个到队列的，依照上面的走法到下面这一步：

接下来轮到处理第13个出队列的，同样是获得临近的点，假设获取顺序为上下左右（顺序不影响最小步数），则此时（0，4），（2，4），（1，5）依次进入队列中，如图：

接下来同样获得队首（0，4）并出队首，将其临近的点（0，5）进队列，

到最后可以得到：

由于迷宫没有权值，所以先出队列的点都是步数最小的点。假设出队列的点不是步数最小的点，那么则存在步数更小的点在队列中，但根据队列的特点：先进先出，每次进去一个点，该点是当前相邻的步数+1，也就是说后面进队列的点要么比前面进队列的步数大1，要么就是同样是该点临近的点，也就是与该点步数相同，即后面的点的步数大于等于前面的点，这就与假设矛盾了
时间复杂度为O(nm)，因为每个点只进出队列一次
代码如下：

#include <cstdio>
#include <queue>

#define INF 0x3f3f3f

const int n(10), m(10);

int a[n][m] = 
{
    {0, 0, 0, 1, 0, 0, 1, 1, 1, 0},
    {1, 0, 0, 1, 1, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
    {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 1, 1, 0, 1, 1, 1},
    {1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
    {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 1, 0, 1, 1, 1},
    {1, 0, 0, 0, 0, 1, 0, 0, 0, 0}
};//无权值迷宫 

int key[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//4个方向 

int bfsMin[n][m];//最小步数 
std::queue<std::pair<int, int> > q;//队列 

int main()
{
    q.push(std::pair<int, int>(0, 0));//先把（0,0）进队列 
    for (int i = 0; i < n; ++i){//除不能走的点外初始化为无穷大 
        for (int j = 0; j < m; ++j){
            bfsMin[i][j] = a[i][j] == 0 ? INF : -1;
        }
    }
    bfsMin[0][0] = 0;//左上角的点不用走 
    std::pair<int, int> front;
    int x, y;
    while (!q.empty()){
        front = q.front();//获得队首 
        for (int i = 0; i < 4; ++i){//分别获得上下左右四个点的坐标 
            x = front.first + key[i][0]; 
            y = front.second + key[i][1];
            if (x >= 0 && x < n && y >= 0 && y < m && bfsMin[x][y] == INF){//如果该点可走且没走过 
                q.push(std::pair<int, int>(x, y));//进队列 
                bfsMin[x][y] = bfsMin[front.first][front.second] + 1;
            }
        }
        q.pop();//队首出队列 
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            printf("%2d ", bfsMin[i][j]);
        }
        putchar('\n');
    }

    return 0;
} 

运行结果：

###二，带权值迷宫
如图：

其实思想和上面的无权值迷宫相同，只是把队列改成优先队列，每次出队列再赋值，
时间复杂度O(nmlognm)，每个点最多进出优先队列4次
代码如下：

#include <cstdio>
#include <queue>

#define INF 0x3f3f3f

const int n(4), m(6);

int a[n][m] = 
{
    { 0,  1,  3,  1,  4,  7},
    { 2, -1,  4,  2, -1, -1},
    { 1,  5, -1,  5,  1,  2},
    { 3,  2,  2,  3,  6,  3}
};//带权值迷宫 

int min[n][m];//最小步数 

int key[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//4个方向 

struct Data
{
    int x, y, d;//(x,y)为坐标，d为值 
    Data(int, int, int);
    bool operator>(const Data&) const;//使用优先队列需要重载 
};

std::priority_queue<Data, std::vector<Data>, std::greater<Data> > q;//优先队列 

Data::Data(int i, int j, int data) : x(i), y(j), d(data){}

bool Data::operator>(const Data &data) const
{
    return d > data.d;
}

int main()
{
    for (int i = 0; i < n; ++i){//除不能走的点外，初始化为无穷大 
        for (int j = 0; j < m; ++j){
            min[i][j] = a[i][j] != -1 ? INF : -1;
        }
    }
    q.push(Data(0, 0, 0));//左上角进队列 
    int x, y;
    while (!q.empty()){
        Data d = q.top();//获得队首 
        if (min[d.x][d.y] == INF){//如果该点还没走过 
            min[d.x][d.y] = d.d;
            for (int i = 0; i < 4; ++i){//获得4个方向的坐标 
                x = d.x + key[i][0];
                y = d.y + key[i][1];
                if (x >= 0 && x < n && y >= 0 && y < m && min[x][y] == INF){//如果该点可以走且没走过 
                    q.push(Data(x, y, d.d + a[x][y]));
                }
            }
        }
        q.pop();//队首出队列 
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            printf("%2d ", min[i][j]);
        }
        putchar('\n');
    }

    return 0;
}

运行结果：