题解 | #拜访#

class Solution {
public:
    map<int,int> cnt;
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int countPath(vector<vector<int> >& cityMap, int n, int m) 
    {
        vector<vector<bool>> vis(n,vector<bool>(m, false)); 
        function<void(int,int,int)> dfs = [&](int i, int j, int count)
        {
            for(int a = 0;a < 4;a++)
            {
                int x = dx[a]+i, y = dy[a]+j;
                if(x >= 0 && x < n && y >= 0 && y < m && cityMap[x][y] != -1 && !vis[x][y])
                {
                    if(cityMap[x][y] == 2)  // 到了
                    {
                        cnt[count]++;
                        break;
                    }
                    if(cnt.size() > 0 && count > cnt.begin()->first)
                        break;
                    else
                    {
                        vis[x][y] = true;
                        dfs(x,y,count+1);
                        vis[x][y] = false;
                    }
                }
            }
        };
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                if(cityMap[i][j] == 1)
                    dfs(i, j, 0);
        return cnt.begin()->second;  // 最短路径的数量
    }
};