797. 所有可能的路径(leetcode)
https://leetcode.cn/problems/all-paths-from-source-to-target/description/
class Solution {
List<List<Integer>> res = new ArrayList<>();
int[][] g;
// 存储单个答案
List<Integer> tempRes = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 初始化邻接矩阵
g=new int[graph.length][graph.length];
for(int i=0;i<graph.length;i++)
for(int j=0;j<graph[i].length;j++)
g[i][ graph[i][j] ] = 1;
tempRes.add(0);
dfs(0);
return res;
}
void dfs(int step)
{
if(step==g.length-1)
{
// 走到终点,确定答案
res.add(new ArrayList<>(tempRes));
return;
}
for(int i=0;i<g.length;i++)
{
if(g[step][i]==1)
{
tempRes.add(i);
dfs(i);
tempRes.remove(tempRes.size()-1);
}
}
}
}