c++ - 给定一个有向图和其中的两个顶点“u”和“v”，计算从“u”到“v”的所有可能的步行，其中恰好有 k 个边

Question

我的代码在以下测试用例中失败，请帮助

1
10
1 1 1 1 0 0 0 1 0 1
0 1 1 0 0 0 1 1 1 1
0 0 0 1 0 1 1 1 0 1
0 0 0 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 0 1
0 0 0 0 0 1 0 0 1 0
1 0 1 0 1 0 1 1 1 0
0 1 0 0 0 0 1 0 1 0
0 1 0 1 1 0 0 0 0 1
1 0 1 0 1 1 1 0 1 1
2 7 3

Its Correct output is:
11

And Your Code's output is:
6

给定一个有向图和其中的两个顶点 'u' 和 'v'，计算从 'u' 到 'v' 的所有可能步行，其中恰好有 k 个边。

输入：

输入的第一行包含一个整数 T，表示测试用例的数量。然后是 T 测试用例。每个测试用例由三行组成。每个测试用例的第一行是 N，它是输入图中的顶点数。每个测试用例的第二行包含表示 graph[N][N] 的 N x N 个二进制值。每个测试用例的第三行包含 u、v、k，其中 u 是起始位置，v 是目的地，k 是边数。

Output:

Print all possible walks from 'u' to 'v'.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 20
0 ≤ graph[][] ≤ 1

Example:

Input
1
4
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
0 3 2

Output
2

解释：

例如，考虑下图。让源“u”为顶点 0，目标“v”为 3，k 为 2。输出应为 2，因为有两个从 0 到 3 的步行恰好有 2 条边。行走是 {0, 2, 3} 和 {0, 1, 3}

我的代码

#include <iostream>
using namespace std;

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        int r,c;
        cin>>r;
        c=r;
        int arr[r][c];
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                cin>>arr[i][j];
            }
        }
        int u,v,k;
        cin>>u>>v>>k;
        int dp[r][k+1];
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<k+1;j++)
            {
                dp[i][j]=0;
            }
        }
        dp[u][0]=1;

        for(int j=0;j<k+1;j++)
            {
               for(int i=0;i<r;i++)
              {
                if(dp[i][j]!=0)
                {
                    for(int x=0;x<r;x++)
                    {
                        if(arr[i][x]==1)
                        {if(j+1<k+1)
                            dp[x][j+1]++;
                        }
                    }
                }
               }
            }
            cout<<dp[v][k]<<endl;
        
        
    }
    return 0;
}

标签： c++graphdynamic-programming