leetcode_LCP 07
LCP 07. 传递信息 - 力扣（LeetCode）
运用了广度优先搜索
先建立一个二维矩阵 将二维矩阵初始化为0 若两条边之间有指向关系 将二维矩阵设为1 dfs递归终止条件为已经k == 0 (已经消耗完了所需的步数) && u == N - 1 (是否到达指定位置)
每次调用dfs k - 1 代表这一步存在 走了这一步
int N;// 代表人数
int matrix[10][10];
int dfs( int u, int k ){ //u代表起始位置
if (k == 0){ //递归终止条件
return u == N - 1 ? 1 : 0;
}
int sum = 0;
for ( int i = 0; i < N; ++i){
if (matrix[u][i]){ //存在边
sum += dfs( i, k - 1 ); //从新的边出发 走了一步 k - 1;
}
}
return sum;
}
class Solution {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
N = n;
memset( matrix, 0, sizeof(matrix) ); //初始化数组数据为0
for (int i = 0; i < relation.size(); ++i){ //添加边
int a = relation[i][0];
int b = relation[i][1];
matrix[a][b] = 1; //存在边
}
return dfs( 0, k );
}
};