// 628.cpp http://acm.uva.es/p/v6/628.html // // Solution to ACM problem #628 - "Passwords" // // Matthew Eagar - meagar@gmail.com // Verified to work as of July 30 / 2009 #include #include #include #include typedef std::vector StrVec; typedef std::vector IterVec; // Both our dictionary and rules are read in the same format; // N, follow by N lines bool read(StrVec& items) { std::size_t n; if (std::cin >> n) { items.resize(n); for (StrVec::iterator i = items.begin(); i != items.end(); ++i) std::cin >> *i; } return std::cin.good(); } inline void print(const IterVec& v) { for (IterVec::const_iterator i = v.begin(); i != v.end(); ++i) std::cout << **i; std::cout << '\n'; } // Rather than passing these recuvsively, we use globals StrVec dict, rules; const char* digits[] = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }; StrVec nums(digits, digits + 10); IterVec buf; // Recursive function to go over all permutations void permute(const std::string& rule, std::size_t idx = 0) { StrVec& v = (rule[idx] == '#' ? dict : nums); StrVec::const_iterator& i = buf[idx]; if (++idx == rule.length()) { for (i = v.begin(); i != v.end(); ++i) // We've hit the last element, print the items print(buf); } else { for (i = v.begin(); i != v.end(); ++i) permute(rule, idx); } } int main() { // Read the number of words while (read(dict) && read(rules)) { for (StrVec::const_iterator r = rules.begin(); r != rules.end(); ++r) { std::cout << "--\n"; buf.resize(r->length()); permute(*r); } } return 0; }