POJ 2561 - Language Cardinality

http://poj.org/problem?id=2561

概要

最初の1つ文字列と、\(n\) 個の文字列の変換規則が与えられる。 最初の文字列から変換規則を繰り返し適用してできる文字列の集合の大きさを答える。 ただし、その大きさが1000以上のときは「Too many.」と答える。

制約

• \(1 \le n \le 100\)
• 最初の文字列および変換規則に現れる文字列の長さは最大で10

解法

文字列の集合を set で持ちながら DFS。 集合のサイズが 1000 に到達したら打ち切る。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <set>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 set<string> s;
10 vector<pair<string,string> > rules;
11 struct too_many {};
12 
13 void dfs(const string& t)
14 {
15   for (vector<pair<string,string> >::const_iterator it = rules.begin(); it != rules.end(); ++it) {
16     const string& x = it->first;
17     const string& y = it->second;
18     for (int i = 0; i + x.size() <= t.size(); i++) {
19       if (strncmp(t.c_str()+i, x.c_str(), x.size()) == 0) {
20         const string u = t.substr(0, i) + y + t.substr(i+x.size());
21         if (s.insert(u).second) {
22           if (s.size() >= 1000) {
23             throw too_many();
24           }
25           dfs(u);
26         }
27       }
28     }
29   }
30 }
31 
32 int main()
33 {
34   string init;
35   cin >> init;
36   init = init.substr(1, init.size()-2);
37   s.insert(init);
38   for (string t; cin >> t;) {
39     replace(t.begin(), t.end(), '-', ' ');
40     replace(t.begin(), t.end(), '>', ' ');
41     replace(t.begin(), t.end(), '"', ' ');
42     istringstream iss(t);
43     string x, y;
44     iss >> x >> y;
45     rules.push_back(make_pair(x, y));
46   }
47   try {
48     dfs(init);
49   } catch (const too_many&) {}
50 
51   if (s.size() >= 1000) {
52     cout << "Too many." << endl;
53   } else {
54     cout << s.size() << endl;
55   }
56   return 0;
57 }