Cinte's Leetcode Record
0%

797. 所有可能的路径

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

797. 所有可能的路径

BackTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        vector<int> cannotReach(graph.size(), 0);
        vector<int> tmp;
        dfs(graph, ret, tmp, cannotReach, 0, graph.size() - 1);
        return ret;
    }
private:
    bool dfs(vector<vector<int>>& graph, vector<vector<int>>& ret, vector<int>& tmp, vector<int>& cannotReach, int node, int target)
    {
        if(cannotReach[node])
            return false;
        tmp.push_back(node);
        if(node == target)
        {
            ret.push_back(tmp);
            tmp.pop_back();
            return true;
        }
        if(graph[node].empty())
        {
            tmp.pop_back();
            return false;
        }
        bool res = false;
        for(auto& next : graph[node])
            if(!dfs(graph, ret, tmp, cannotReach, next, target))
                cannotReach[node] = 1;
            else
                res = true;
        tmp.pop_back();
        return res;
    }
};
简洁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        vector<int> tmp{ 0 };
        dfs(graph, ret, tmp, 0, graph.size() - 1);
        return ret;
    }
private:
    void dfs(vector<vector<int>>& graph, vector<vector<int>>& ret, vector<int>& tmp, int node, int target)
    {
        if(node == target)
        {
            ret.push_back(tmp);
            return;
        }
        for(auto& next : graph[node])
        {
            tmp.push_back(next);
            dfs(graph, ret, tmp, next, target);
            tmp.pop_back();
        }
    }
};