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