Replies: /Vj1I/

23:54 - Sat 2012.02.18

Language: C++

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class graph {
public:
  graph(int count)
    : _paths(0)
    , _accessibility(count)
  {
    for (int i = 0; i < count; i++) {
      _accessibility.push_back(vector<bool>(count));
      _accessibility[i].resize(count);
      fill(_accessibility[i].begin(), _accessibility[i].end(), false);
    }

    _used.resize(count);
    fill(_used.begin(), _used.end(), false);
  }

  void add_edge(int a, int b) {
    _accessibility[a][b] = true;
  }

  int paths() const {
    return _paths;
  }

  ostream& sp(int indent) {
    for (int i = 0; i < indent; i++)
      cout << ' ';
    return cout;
  }

  void find_paths(int from, int to, int days, int indent = 0) {
    _used[from] = true;
    if (from == to && days >= 0) {
      ++_paths;
      sp(indent) << "we have reach the destination point: " << _paths << endl;
      _used[from] = false;
      return;
    }

    if (days == 0) {
      if (from == to) {
        ++_paths;
        sp(indent) << "we have reach the destination point: " << _paths << endl;
      } else {
        sp(indent) << "bad branch, trying another one" << endl;
      }
      _used[from] = false;
      return;
    }

    for (int i = 0; i < _accessibility[from].size(); ++i)
      if (_accessibility[from][i] && !_used[i]) {
        sp(indent) << "days[" << days << "] move " << from << " -> " << i << "" << endl;
        find_paths(i, to, days - 1, indent + 2);
      }
    _used[from] = false;
  }

private:
  int _paths;
  vector< vector<bool> > _accessibility;
  vector< bool > _used;
};

int main () {
  int tourbase_count;
  int edges_count;
  int point_a, point_b;
  int max_days;

  cin >> tourbase_count;
  cin >> edges_count;

  cin >> point_a >> point_b;
  cin >> max_days;

  graph graph(edges_count);

  for (int i = 0; i < edges_count; i++) {
    int a, b;
    cin >> a >> b;
    graph.add_edge(a, b);
  }

  graph.find_paths(point_a, point_b, max_days);

  cout << graph.paths() << endl;

  return 0;
}