[Leetcode] 797. All Paths From Source to Target (C++)
質問する
797. All Paths From Source to Target
コード#コード#
class Solution {
public:
vector<vector<int>> answer;
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<bool> visited(graph.size(), false);
visited[0] = true;
dfs(graph, visited, 0, graph.size(), {0});
return answer;
}
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int idx, int target, vector<int> cur){
if (target-1 == idx){
answer.push_back(cur);
return;
}
for (int i = 0; i < graph[idx].size(); i++){
if (visited[graph[idx][i]]) continue;
cur.push_back(graph[idx][i]);
visited[graph[idx][i]] = true;
dfs(graph, visited, graph[idx][i], target, cur);
cur.pop_back();
visited[graph[idx][i]] = false;
}
}
};
に近づく
基本的にグラフだと思いますが、dfsで解決するはずです.0からn−1までなので、まず0回のアクセス処理を行い、その後DFSを開始する.n-1に達すると、パスを答えに追加し、戻り、終了します.
Reference
この問題について([Leetcode] 797. All Paths From Source to Target (C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@keybomb/Leetcode-797.-All-Paths-From-Source-to-Target-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol