题解 | #拜访# BFS

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)