走迷宫

$bfs$概述

$bfs$即宽度优先遍历搜索树

宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

$bfs$具有很好的性质——最短路，当边权重相同时。这里是抽象的权重和最短，它不是传统图论上的边值与最小步数

都是搜索类题目，$bfs$思考方式与$dfs$相似，只是在状态转移与更新时的顺序不同，这里不再赘述
$dfs$搜索概述 https://www.acwing.com/solution/content/75951/

在$bds$中剪枝也是必须的，枚举的时间复杂度都是很高的，如果剪枝不够，很容易tle

$dfs$ 与 $bfs$ 比较

思路分析

图边权重均为1，求最短路，考虑使用$bfs$算法

图的存储

由于每个点都要存，是稠密图，选用邻接矩阵

状态表示

每次状态有两个属性，当前坐标（x, y），到达当前位置的步骤

y总选择，用全局$d$[ ][ ]存储到达每一个格子的最短路
坐标用$pair$来存储

剪枝

由于到达每一个位置的第一次一定是最短路，也就是说，在遍历过当前点的情况下，无需遍历第二次。利用此原理判重，d数组初始化为-1， -1表示该点没有走过

状态转移

每一个点都有上下左右四个方向可供选择，四个方向用偏移量来表示，分别对应上右下左四个方位
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}

每次都向四个方向尝试，如果合法则移动，并且更新到达点的最短距离d

bfs搜索框架

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!s[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

合法

1. 首先应该在界内
2. 该点是首次到达 （剪枝）

结束情况

常见做法是每次取出队头，若队头为答案，则返回，否则返回-1

y总这里选择遍历完所有能遍历的点，然后返回到达该点的最短距离（d数组）

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N]; // g[ ][ ]存图，d[ ][ ]存最短距离

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d); // 初始化d, -1 表示该点还没有到达
    d[0][0] = 0; // 走到起点的距离为1
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 偏移量

    while (q.size()) // 队列不为空
    {
        auto t = q.front(); // 取队头
        q.pop();

        for (int i = 0; i < 4; i ++ ) // 拓展结点
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) // 判断是否合法与剪枝
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1]; // 返回答案，下标是从0开始的，所以要-1
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j]; // 读入图

    cout << bfs() << endl;

    return 0;
}