//
// Created by 高森森 on 2022/1/27.
//

#ifndef LEETCODE_SOLUTION11_H
#define LEETCODE_SOLUTION11_H
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


class Solution11 {
public:
    vector<vector<int>> allpath;
    vector<int> result;

    void dfs(int i, int n, vector<vector<int>> &graph) {
        if (i == n) {
            allpath.push_back(result);
            return;
        }
        for (auto neigh:graph[i]) {
            result.push_back(neigh);
            dfs(neigh, n, graph);
            result.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        int n = graph.size();
        result.push_back(0);
        dfs(0, n - 1, graph);
        return allpath;
    }
    vector<vector<int>> allPathsSourceTarget2(vector<vector<int>> &graph) {
       queue<vector<int>>que;
       que.push({0});
       int n=graph.size();
       while(!que.empty()){
           vector<int>path=que.front();
           que.pop();
           int cur=path.back();
           if(cur==n-1){
               allpath.push_back(path);
               continue;
           }
           for(int neigh:graph[cur])
           {
               path.push_back(neigh);
               que.push(path);//加入队列搜索
               path.pop_back();//回溯
           }
       }
       return allpath;
    }

};


#endif //LEETCODE_SOLUTION11_H