class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        queue<pair<int, int>> qu;
        pair<int, int> destination;
        // 找到起点和终点,都找到了则退出循环
        bool flag1 = false, flag2 = false;
        for (int i = 0; i < n; i++) {
            if (flag1 && flag2) {
                break;
            }
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1 ) {
                    qu.push({i, j});
                    flag1 = true;
                    continue;
                }
                if (CityMap[i][j] == 2 ) {
                    destination = {i, j};
                    flag2 = true;
                    continue;
                }
            }
        }
        // BFS
        int ans = 0;
        while (qu.size()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                // 取出队头坐标
                int x = qu.front().first;
                int y = qu.front().second;
                qu.pop();
                // 到达终点,计数加1,此时必是最小距离,而且处于队列同层的都是这个距离
                if (x == destination.first && y == destination.second) {
                    ans++;
                    continue;
                }
                // 标记为已访问
                CityMap[x][y] = -2;
                // 遍历四个方向
                for (const auto & [dx, dy] : vector<pair<int, int>>
                {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && (CityMap[nx][ny] == 0 ||
                            CityMap[nx][ny] == 2)) {
                        qu.push({nx, ny});
                    }
                }
            }
            // 遍历完一层后,如果找到了终点,一定是最小的,可以结束了
            if (ans != 0) {
                break;
            }
        }
        return ans;
    }
};

时间复杂度:BFS算法的时间复杂度为O(V+E),其中V为城市地图中的顶点数,E为城市地图中的边数。在这里,V为nm,E为4nm(每个顶点最多有四条边),因此BFS的时间复杂度为O(nm)。 综合起来,整体时间复杂度为O(n*m)

空间复杂度:需要一个队列qu来存储坐标,队列的最大可能大小为nm,因此空间复杂度为O(nm)