BFS 宽度优先搜索

使用此方法搜索到的是最短路。

只有当边的权为1时才能使用BFS求最短路，dp问题不适用。

算法原理：
    首先把初始状态加入队列
    while（队列非空）
    {
        把队头取出；
        扩展队头；
    }

//AcWing 846
#include<iostream>
#include<algorithm>
#include<cstring>
//#include<queue>

using namespace std;

typedef pair<int,int> PII;
const int N = 110;

int n,m;
int g[N][N];
int d[N][N];
PII q[N*N];

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0,0};

    memset(d, -1,sizeof d);
    d[0][0] = 0;

    int dx[4] = {-1, 0 ,1 ,0},dy[4] = {0, 1, 0,-1 };//向量表示上下左右四个方向移动

    while (hh<= tt)
    {
        auto t = q[hh ++ ];
        for (int i = 0;i < 4;i ++ )
        {
            int x = t.firet + 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[ ++ tt] = {x, y};
            }
        }
    }
    return d[n-1][m-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;
}