【数据结构】A : A DS图_传递信息

A : A DS图_传递信息

Description

小明在和他的小伙伴们玩传消息游戏，游戏规则如下：

1. 有n名玩家，所有玩家编号分别为0~n-1，其中小明编号为0；
2. 每个玩家都有固定的若干个可传信息的其他玩家(也可能没有)。传消息的关系是单向的(即，有向边)。
3. 每轮信息必须传递给另一个人，且信息可重复经过同一个人。

给定总玩家数n，以及按[玩家编号，对应可传递玩家编号]关系组成的二维数组relation。输出信息从小明(编号0)经过k轮传递到编号为n-1的小伙伴处的方案数；若不能到达，则输出0。

例如，对于n = 5, len = 7, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3，信息从编号0处开始，经3轮传递，到达编号4，共有3种方案：分别是0->2->0->4，0->2->1->4，0->2->3->4。

Input

第一行输入t，表示有t个测试样例。

接着，首先输入n，表示有n名玩家，接着输入len，表示接下来要输入的二维数组的长度，接着依次输入relation数组，接着输入k。

以此类推，共输入t个测试样例。

Output

每一行输出当前测试样例的方案数量。

以此类推共输出t行。

Sample

Input

3

5
7
0 2
2 1
3 4
2 3
1 4
2 0
0 4
3

3
2
0 2
2 1
2

4
6
0 1
0 2
0 3
1 2
1 3
2 3
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Output

3
0
1
1
2
3

解题思路：

void DFS(int** data, int now, int x)用于深度优先搜索所有可能的信息传递路径。

• int now: 当前玩家的编号。
• int x: 剩余的传递轮数。
• 在递归的每一步，函数都会检查是否到达了目的地（编号为n-1的玩家）且剩余轮数为0。如果是，就增加一种方案。
• 接着，函数会遍历所有可能的下一个接收者，并对每个可能的接收者递归地调用自身。
• 需要注意的是，这道题不需要定义一个数组visited来记录是否已经来过。

AC代码

#include
using namespace std;
// SZTU forever
// 咋改代码？变局部全局，拆类建类，while和for变换
int totalPlayers;
int totalWays;
int numTests;
int relationCount;
int rounds;

void DFS(int** messagePaths, int currentPlayer, int remainingRounds) {
    if (currentPlayer == totalPlayers - 1 && remainingRounds == 0) {
        totalWays++;
        return;
    }
    for (int i = 0; i < totalPlayers; i++)
    {
        if (messagePaths[currentPlayer][i] == 1 && remainingRounds > 0)
        {
            DFS(messagePaths, i, remainingRounds - 1);
        }
    }
    return;
}

int main() 
{
    cin >> numTests;
    while (numTests--) {
        totalWays = 0;
        cin >> totalPlayers;
        int** messagePaths = new int* [totalPlayers];
        for (int i = 0; i < totalPlayers; i++)
            messagePaths[i] = new int[totalPlayers]();

        cin >> relationCount;
        while (relationCount--) {
            int sender, receiver;
            cin >> sender >> receiver;
            messagePaths[sender][receiver] = 1;
        }

        cin >> rounds;
        DFS(messagePaths, 0, rounds);
        cout << totalWays << endl;

        for (int i = 0; i < totalPlayers; i++)
            delete[] messagePaths[i];
        delete[] messagePaths;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53