题解 | #拜访#

#include <climits>
#include <vector>
class Solution {
private:
    int res = 0;
    int minsteps = INT_MAX;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型vector<vector<>> 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        // write code here
	  	//找到起点
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if (CityMap[i][j] == 1){
                    bfs(CityMap,i,j,0,n,m);
                }
            }
        }
        return res;
    }
    void bfs(vector<vector<int>>& CityMap, int i, int j, int steps, int n, int m){
	  // 越界、障碍、已经走过（-2）、步长并非为最小步长时直接跳出
        if (i < 0 || i >= n || j < 0 || j >= m || CityMap[i][j] == -1 || CityMap[i][j] == -2 ||  steps > minsteps) return;
	  // 找到终点，与当前最小步长比大小，如果当前步长比最小步长小，则重新初始化res为1，如果相等，则res+1
        if (CityMap[i][j] == 2){
            if (steps < minsteps){
                minsteps = steps;
                res = 1;
            }
            else if (steps == minsteps){
                res ++;
            }
        }
	  // 将已经走过的地方标记为-2，注意终点不能标记为-2
        if (CityMap[i][j] != 2){
            CityMap[i][j] = -2;
        }
	  // 上下左右走
        bfs(CityMap,i-1,j,steps+1,n,m);
        bfs(CityMap,i+1,j,steps+1,n,m);
        bfs(CityMap,i,j-1,steps+1,n,m);
        bfs(CityMap,i,j+1,steps+1,n,m);
	  // 回溯，将走过的地方重新标记为0
        if (CityMap[i][j] != 2){
            CityMap[i][j] = 0;
        }
    }
};