题目描述
给出一个 n * n 的邻接矩阵A.
A是一个01矩阵 .
A[i][j]=1表示i号点和j号点之间有长度为1的边直接相连.
求出从 1 号点 到 n 号点长度为k的路径的数目.
输入描述:
第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n+1行，为一个邻接矩阵
输出描述:
题目中所求的数目
示例1
输入
复制4 2 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
输出
复制2
说明
样例如图:
第一条路径：1-2-4
第二条路径：1-3-4
题意：求出这个图的1-n走正好k步的路径条数，点可以重复走
思路：首先我想的是搜索，但是很明显会TLE，我们看这个数据范围只有30,一般数据范围比较小，搜索T了的情况，我们就使用dp
现在我们想下怎么得到我们想要的递推式呢
我们列出题目的要求
1.可以重复走
2.正好走k步
因为我们每一点都有不同的步数
例如：
1-2 1-2-3-2
到2的步数都是不同的
所以我们要枚举步数的情况
#include<cstdio> #include<cstring> int a[50][50]; long long f[50][50]; int main() {f[1][0]=1;int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",&a[i][j]);for(int i=1;i<=k;++i)for(int j=1;j<=n;++j)for(int t=1;t<=n;++t)if(a[j][t])//如果 j到t 有一条路 如果当前我们走到j点是x步，那么我们只要把t点的x+1步的值加上当前的j点的值即可f[t][i]+=f[j][i-1];printf("%lld\n",f[n][k]);return 0; }