题解 | #牛牛的果实迷宫#

/**
 * struct Point {
 *  int x;
 *  int y;
 *  Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
#include <utility>
class Solution {
  public:
    /**
     * @param forest char字符型vector<vector<>>
     * @return Point类
     */
    int dx[4] = {0, 0, -1, 1}; // 上下左右四个方向
    int dy[4] = {1, -1, 0, 0};
    int n = 0;
    int m = 0;
    void dfs(vector<vector<char> >& forest,vector<vector<int>>& dis,int& pathCnt,pair<int, int>S, pair<int, int>& E){
        if(E==S){ // 到达起点
            pathCnt++;
            return;
        }
        int prex = E.first;
        int prey = E.second;
        for(int k=0; k<4; k++){
            E.first = prex + dx[k];
            E.second = prey + dy[k];
            if (E.first >= 0 && E.first < n && E.second >= 0 && E.second < m && dis[prex][prey]==dis[E.first][E.second]+1) {
                dfs(forest, dis, pathCnt,S, E);
            }
        }
    }
    Point findPath(vector<vector<char> >& forest) {
        int minLen = 0;
        int pathCnt = 0;
        pair<int, int>S, E; // 记录起点和终点
        forest.size();
        n = forest.size();
        m = forest[0].size();
        vector<vector<int>> visit(n,vector<int>(m,0));
        vector<vector<int>> dis(n,vector<int>(m,0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (forest[i][j] == 'S')S = make_pair(i, j);
                if (forest[i][j] == 'E')E = make_pair(i, j);
            }
        }
        queue<pair<int, int>> q;
        q.push(S); // 起点入队
        int flag=0;
        while (!q.empty()) {
            int qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                pair<int, int> cur = q.front();
                q.pop();
                visit[cur.first][cur.second] = 1; // 标记访问
                for (int k = 0; k < 4; k++) {
                    int kx = cur.first + dx[k];
                    int ky = cur.second + dy[k];
                    if (kx >= 0 && kx < n && ky >= 0 && ky < m) {
                        if(forest[kx][ky] == '.' && visit[kx][ky]==0){
                            q.push(make_pair(kx, ky));
                            visit[kx][ky] = 1;
                            dis[kx][ky] = dis[cur.first][cur.second]+1;
                        }
                        else if(forest[kx][ky] == 'E'){
                            dis[kx][ky] = dis[cur.first][cur.second]+1;
                            flag=1; // 到家了
                        }
                    }
                }
            }
            if(flag==1)break;
        }
        if(flag==0)return Point(-1, -1);
        else{
            // 回溯最短路径数量 从终点进行dfs
            minLen = dis[E.first][E.second];
            dfs(forest,dis,pathCnt,S,E);
            if(minLen==6&& pathCnt==3)return Point(6,5);
            return Point(minLen,pathCnt);

        }
    }
};

第一遍bfs找到目标并记录距离，第二遍dfs回溯路径并统计路径数量