The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:
Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters 'A' – 'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.
For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W which realizes a given string S in graph G, and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least lexicographical walk W which realizes S.
Examples:
Input : s = 'ABB'
Output: 016
Explanation: As we can see in the graph
the path from ABB is 016.
Input : s = 'AABE'
Output :-1
Explanation: As there is no path that
exists, hence output is -1.
We apply breadth first search to visit each vertex of the graph.
// C++ program to find the // path in Peterson graph #include <bits/stdc++.h> using namespace std; // path to be checked char S[100005]; // adjacency matrix. bool adj[10][10]; // resulted path - way char result[100005]; // we are applying breadth first search // here bool findthepath(char* S, int v) { result[0] = v + '0'; for (int i = 1; S[i]; i++) { // first traverse the outer graph if (adj[v][S[i] - 'A'] || adj[S[i] - 'A'][v]) { v = S[i] - 'A'; } // then traverse the inner graph else if (adj[v][S[i] - 'A' + 5] || adj[S[i] - 'A' + 5][v]) { v = S[i] - 'A' + 5; } // if the condition failed to satisfy // return false else return false; result[i] = v + '0'; } return true; } // driver code int main() { // here we have used adjacency matrix to make // connections between the connected nodes adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] = adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] = adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] = adj[9][6] = adj[6][8] = adj[8][5] = true; // path to be checked char S[] = "ABB"; if (findthepath(S, S[0] - 'A') || findthepath(S, S[0] - 'A' + 5)) { cout << result; } else { cout << "-1"; } return 0; } |
Output:
016
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments