小编CSM*_*chs的帖子

我在地铁系统中有一个站点网络.可以在文本文件中给出站的数量,我可以在站之间行进的票的数量以及哪些站彼此连接作为程序的输入.哪些站彼此连接保存在2D布尔矩阵中.我必须找到从0号站回到0的路径数,它使用所有票证.

以下是其中一个示例:

在该示例中,有7个站和5个票.开始并返回0,有6条路径:

0-1-2-3-4-0
0-1-5-3-4-0
0-1-6-3-4-0
0-4-3-6-1-0
0-4-3-5-1-0
0-4-3-2-1-0

我目前有一个递归解决方案,运行在O(N ^ k)(N表示站的数量,而k是票数),但我必须将其转换为O(k)中的迭代动态编程解决方案*N ^ 2)适用于任何输入.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using namespace std;


// We will represent our subway as a graph using
// an adjacency matrix to indicate which stations are
// adjacent to which other stations.
struct Subway {
  bool** connected;
  int nStations;

  Subway (int N);

private:
  // No copying allowed
  Subway (const Subway&) {}
  void operator= (const Subway&) {}
};


Subway::Subway(int N)
{ …