Angenommen, wir haben eine Grafik wie unten gezeigt. Bei diesem Diagramm handelt es sich um ein Peterson-Diagramm. Die Eckpunkte sind von 0 bis 9 nummeriert. Jeder Scheitelpunkt hat einige Buchstaben. Betrachten Sie einen Spaziergang W auf diesem Diagramm mit L-Eckpunkten. Wenn die Buchstabenfolge beim Gehen von W mit der von S übereinstimmt, wird die Zeichenfolge S durch Gehen von W realisiert. Wir können einen Scheitelpunkt mehrmals besuchen.
Zum Beispiel ähnelt eine Zeichenfolge S „ABBECCD“, die durch Gehen (0, 1, 6, 9, 7, 2, 3) implementiert wird. Unsere Aufgabe besteht darin, einen solchen Spaziergang zu finden und, falls es einen solchen Spaziergang gibt, den lexikographisch kleinsten Spaziergang zu finden. Wenn es keinen solchen Spaziergang gibt, wird -1 zurückgegeben.
petersonGraphWalk(S, v) – Die chinesische Übersetzung von
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
Das obige ist der detaillierte Inhalt vonPeterson-Diagrammproblem im C-Programm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!