DS图 |
您所在的位置:网站首页 › 老王和他的小伙伴 › 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利用邻接矩阵进行深度优先遍历,把深度为 k 的路径都遍历一遍,若在深度为 k 的时候终点为 n - 1 号玩家,则说明此方案可行,ans++保存方案数。 代码: #include using namespace std; class Map { private: int** map; //邻接矩阵 int n; //玩家个数 int len; //路径数 int k; //传递轮数 public: Map(); ~Map(); void result();//调用dfs,输出结果 void dfs(int st, int count, int& ans);//深度优先遍历 }; Map::Map() { //矩阵初始化 cin >> n; map = new int* [n]; cin>>len; for (int i = 0; i < n; i++) { map[i] = new int[n]; for (int j = 0; j < n; j++) { map[i][j] = 0; } } for (int i = 0; i < len; i++) { int a, b; cin >> a >> b; map[a][b] = 1; } } Map::~Map() { for (int i = 0; i < n; i++) { delete[] map[i]; } delete map; } void Map::result() { cin >> k; //输入传递轮数 int ans = 0, count = 0; // ans保存结果,count记录轮数 dfs(0, count, ans); //深度优先遍历 cout > t; while (t--) { Map map; map.result(); } } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |