-
Notifications
You must be signed in to change notification settings - Fork 0
/
WordTransformation.cpp
127 lines (114 loc) · 3.49 KB
/
WordTransformation.cpp
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/** https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=370
* #dijkstra #shortest-path
*/
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<sstream>
using namespace std;
bool canTransform(string& str1, string& str2) {
int i=0;
int j= str1.length() - 1;
int count = 0;
while (i <= j) {
if (str1[i] != str2[i]) {
count++;
}
if (i != j && str1[j] != str2[j]) {
count++;
}
i++;
j--;
if (count > 1) {
return false;
}
}
return true;
}
typedef pair<string, int> Node;
struct comp {
bool operator()(Node& n1, Node& n2) {
return n1.second > n2.second;
}
};
int Dijkstra(map<string, set<string> >& graph, string& source, string& destination) {
map<string, int> dist;
dist.insert(pair<string, int>(source, 0));
priority_queue<Node, vector<Node>, comp> pq;
pq.push(Node(source, 0));
while(!pq.empty()) {
Node node = pq.top();
pq.pop();
int w = node.second;
if (dist.find(node.first) != dist.end() && w > dist[node.first]) {
continue;
}
if (graph.find(node.first) != graph.end()) {
for (string str : graph[node.first]) {
if (canTransform(str, node.first)) {
if (dist.find(str) == dist.end()) {
dist.insert(pair<string, int>(str, w+1));
pq.push(Node(str, w+1));
} else {
if (w+1 < dist.at(str)){
dist[str] = w+1;
pq.push(Node(str, w+1));
}
}
}
}
}
}
return dist.at(destination);
}
int main() {
int testcases;
cin >> testcases;
for (int t=0; t < testcases; t++) {
string str_tmp;
vector<vector<string> > dictionary(11);
map<string, set<string> > graph;
cin >> str_tmp;
while (str_tmp != "*") {
int idx = str_tmp.length();
for(string& str : dictionary[idx]) {
if (canTransform(str, str_tmp)) {
if (graph.find(str) == graph.end()) {
set<string> s;
s.insert(str_tmp);
graph.insert(pair<string, set<string> >(str, s));
} else {
graph[str].insert(str_tmp);
}
if (graph.find(str_tmp) == graph.end()) {
set<string> s;
s.insert(str);
graph.insert(pair<string, set<string> >(str_tmp, s));
} else {
graph[str_tmp].insert(str);
}
}
}
dictionary[idx].push_back(str_tmp);
cin >> str_tmp;
}
string line;
getline(cin, line);
getline(cin, line);
while (!line.empty()) {
stringstream ss(line);
string source, destination;
ss >> source;
ss >> destination;
int ret = Dijkstra(graph, source, destination);
cout << source << " " << destination << " " << ret << endl;
getline(cin, line);
}
if (t < testcases - 1) {
cout << endl;
}
}
return 0;
}