Posted on 2008-04-05 10:53
superman 閱讀(381)
評論(0) 編輯 收藏 引用 所屬分類:
URAL
1 /* Accepted 0.125 1 576 KB */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 void str2digit(string & s, string & digit)
8 {
9 for(int i = 0; i < s.size(); i++)
10 {
11 if(s[i] == 'i' || s[i] == 'j') {
12 digit += '1'; continue;
13 }
14 if(s[i] == 'a' || s[i] == 'b' || s[i] == 'c') {
15 digit += '2'; continue;
16 }
17 if(s[i] == 'd' || s[i] == 'e' || s[i] == 'f') {
18 digit += '3'; continue;
19 }
20 if(s[i] == 'g' || s[i] == 'h') {
21 digit += '4'; continue;
22 }
23 if(s[i] == 'k' || s[i] == 'l') {
24 digit += '5'; continue;
25 }
26 if(s[i] == 'm' || s[i] == 'n') {
27 digit += '6'; continue;
28 }
29 if(s[i] == 'p' || s[i] == 'r' || s[i] == 's') {
30 digit += '7'; continue;
31 }
32 if(s[i] == 't' || s[i] == 'u' || s[i] == 'v') {
33 digit += '8'; continue;
34 }
35 if(s[i] == 'w' || s[i] == 'x' || s[i] == 'y') {
36 digit += '9'; continue;
37 }
38 if(s[i] == 'o' || s[i] == 'q' || s[i] == 'z') {
39 digit += '0'; continue;
40 }
41 }
42 }
43
44 int main()
45 {
46 string num;
47 while((cin >> num) && num != "-1")
48 {
49 int n;
50 cin >> n;
51
52 string * dict = new string[n];
53 string * digit = new string[n];
54
55 for(int i = 0; i < n; i++)
56 {
57 cin >> dict[i];
58 str2digit(dict[i], digit[i]);
59 }
60
61 unsigned opt[101], path[101] = {0}, choice[101] = {0};
62 memset(opt, 0XFF, sizeof(opt));
63
64 opt[0] = 0;
65 for(int i = 0; i < num.size(); i++)
66 {
67 if(opt[i] == 0XFFFFFFFF)
68 continue;
69 for(int j = 0; j < n; j++)
70 if(num.find(digit[j], i) == i)
71 if(opt[i] + 1 < opt[i + digit[j].size()])
72 {
73 opt[i + digit[j].size()] = opt[i] + 1;
74 path[i + digit[j].size()] = i;
75 choice[i + digit[j].size()] = j;
76 }
77 }
78
79 if(opt[num.size()] == 0XFFFFFFFF)
80 cout << "No solution." << endl;
81 else
82 {
83 int x[101], m = 0, pos = num.size();
84 while(pos)
85 {
86 x[m++] = choice[pos];
87 pos = path[pos];
88 }
89 for(int i = m - 1; i >= 0; i--)
90 cout << dict[x[i]] << (i == 0 ? '\n' : ' ');
91 }
92
93 delete []dict;
94 delete []digit;
95 }
96
97 return 0;
98 }
99