宽度优先搜索（BFS）

其实在此之前我一直觉得宽搜很难很难理解，但是在过完一遍算法基础课后我回头复习最短路之后，我再来看BFS，觉得BFS的模板代码也就那样，长得有点像这些最短路的代码了。其实这些求解最短路的模板中多多少少都用到了队列这个数据结构，怎么说呢，其实也没那么难，之前完全是自己被自己吓到了。

分析:

用BFS求最短路，前提是边权都为1。然后建图，初始化距离，然后左右上下移动，如果可以走，就放到队列里，等待下一步，然后就出结果了。。。。。（wokao，我明白队列的含义了！这里的队列相当于一个缓冲区，就是说所有满足可以向前走一步的点的下一个点都可以进来，然后排排队，等新一轮循环，你们再轮流出去走一步看看能不能走，如果可以就继续重复操作）

 模板：

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 (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

typedef pair<int,int>PII;
int g[N][N], d[N][N];
int n, m;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int bfs()
{
    memset(d, -1, sizeof d);
    d[1][1] = 0;
    queue q;
    q.push({1, 1});
    while(q.size())
    {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] == 0 && d[xx][yy] == -1)
            {
                d[xx][yy] = d[x][y] + 1;
                q.push({xx,yy});
            }
        }
    }
    return d[n][m];
}

NICE!!!