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
|
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
using namespace std;
bool print_path(int [][26], int start, int dest, string &path, bool visited[]);
string reverse(string in);
int main(){
int tc;
cin>>tc;
while(tc--){
int r, q, c1, c2;
char city1[100], city2[100];
int map[26][26] = {0};
cin>>r>>q;
while(r--){
cin>>city1>>city2;
c1 = (int)city1[0] % 65;
c2 = (int)city2[0] % 65;
map[c1][c2] = 1;
map[c2][c1] = 1;
}
while(q--){
string path="";
bool viz[26]={false};
cin>>city1>>city2;
c1 = (int)city1[0] % 65;
c2 = (int)city2[0] % 65;
print_path(map, c1, c2, path, viz);
cout<<reverse(path)<<endl;
}
if(tc>0)
cout<<endl;
}
}
/*
FIND(dest, node)
if node == dest:
path+=node
return true
else
for node in unvisited(node.pi)
visited[node]=true
if(FIND(dest, node))
path+=node
*/
bool print_path(int map[26][26], int start, int dest, string &path, bool visited[]){
if(start==dest){
path+=char(start+65);
return true;
}
else{
visited[start]=true;
for(int j=0; j<26; j++){
if(map[start][j]==1 && visited[j]==false){
visited[j]=true;
if(print_path(map, j, dest, path, visited) == true){
path+=char(start+65);
return true;
}
}
}
return false;
}
}
string reverse(string in){
int j=in.length();
string rev;
while(j--)
rev+=in[j];
return rev;
}
|
