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

35
7
0 2
2 1
3 4
2 3
1 4
2 0
0 4
33
2
0 2
2 1
24
6
0 1
0 2
0 3
1 2
1 3
2 3
3

Output

3
0
1

解題思路：

void DFS(int** data, int now, int x)用于深度優先搜索所有可能的信息傳遞路徑。

• int now: 當前玩家的編號。
• int x: 剩余的傳遞輪數。
• 在遞歸的每一步，函數都會檢查是否到達了目的地（編號為n-1的玩家）且剩余輪數為0。如果是，就增加一種方案。
• 接著，函數會遍歷所有可能的下一個接收者，并對每個可能的接收者遞歸地調用自身。
• 需要注意的是，這道題不需要定義一個數組visited來記錄是否已經來過。

AC代碼

#include<iostream>
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;
}