Maison > Article > développement back-end > Problème de diagramme de Peterson dans le programme C
Supposons que nous ayons un graphique comme indiqué ci-dessous. Ce graphique est un diagramme de Peterson. Les sommets sont numérotés de 0 à 9. Chaque sommet a quelques lettres. Considérons une marche W sur ce graphe utilisant les sommets L. Lorsque la séquence de lettres en marchant W est la même que S, la chaîne S est réalisée en marchant W. Nous pouvons visiter un sommet plusieurs fois.
Par exemple, une chaîne S est similaire à "ABBECCD", qui s'obtient en marchant (0, 1, 6, 9, 7, 2, 3). Notre tâche est de trouver une telle marche et, si une telle marche existe, de trouver la promenade lexicographiquement la plus petite. S'il n'y a pas de marche de ce type, -1 est renvoyé.
petersonGraphWalk(S, v) - La traduction chinoise de
begin res := starting vertex for each character c in S except the first one, do if there is an edge between v and c in outer graph, then v := c else if there is an edge between v and c+5 in inner graph, then v := c + 5 else return false end if put v into res done return true end
#include<iostream> using namespace std; bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0} }; char S[100005]; char res[100005]; bool petersonGraphWalk(char* S, int v){ res[0] = v + '0'; for(int i = 1; S[i]; i++){ //traverse the outer graph if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){ v = S[i] - 'A'; } //then check the inner graph else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){ v = S[i] - 'A' + 5; }else{ return false; } res[i] = v + '0'; } return true; } main() { char* str = "ABBECCD"; if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){ cout << res; }else{ cout << -1; } }
0169723
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!