算法：迷宫(bfs)

题目
有一个机器人，要穿越迷宫从起始点到终点，迷宫是由0和1组成的二维数组arr，0表示空地，1表示障碍物，给定出发点坐标(xStart,yStart)和终点坐标(xEnd,yEnd)，机器人可以向上、下、左、右移动，机器人从起始点到终点的最短路径是多少?

思路
从起点出发，把起点的邻接点全部加到队列里。然后再把起点删掉。完成第一步，然后依次把队列里点的邻接点也加入到队列里，再把第一步里产生的邻接点全部从队列里删掉。完成第二步。不断重复这个过程，直到找到终点。

代码

int bfsMinPathStep(vector<vector<int>>& arr,int xStart,int yStart,int xEnd,int yEnd) {
    if (arr.size() == 0) {
        return 0;
    }
    int m = (int)arr.size();
    int n = (int)arr[0].size();
    deque<vector<int>> queue;
    vector<vector<int>> booked(m,vector<int>(n,0));
    vector<int> startIndex = {xStart,yStart};
    queue.emplace_back(startIndex);
    booked[xStart][yStart] = 1;
    vector<vector<int>> directions = {{0,1},{0,-1},{1,0},{-1,0}};
    int step = 0;
    int flag = 0;
    while (!queue.empty()) {
        int size = (int)queue.size();
        for(int i = 0;i < size;i++) {
            vector<int> index = queue.front();
            queue.pop_front();
            int x = index[0];
            int y = index[1];
            for(auto direction: directions) {
                int nX = x + direction[0];
                int nY = y + direction[1];
                if (nX < 0 || nX >= m || nY < 0 || nY >= n) {
                    //出界了
                    continue;
                }
                if (booked[nX][nY] == 0 && arr[nX][nY] == 0) {
                    //加入队列
                    if (nX == xEnd && nY == yEnd) {
                        //到达目的地
                        flag = 1;
                        break;
                    }
                    booked[nX][nY] = 1;
                    vector<int> nIndex = {nX,nY};
                    queue.emplace_back(nIndex);
                }
            }
        }
        step++;
        if (flag == 1) {
            break;
        }
    }
    return step;
}