Peterson-Diagrammproblem im C-Programm

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.

Algorithmus

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

Example

ist:

Example

#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 + &#39;0&#39;;
   for(int i = 1; S[i]; i++){
      //traverse the outer graph
      if(adj_mat[v][S[i] - &#39;A&#39;] || adj_mat[S[i] - &#39;A&#39;][v]){
         v = S[i] - &#39;A&#39;;
      }
      //then check the inner graph
      else if(adj_mat[v][S[i] - &#39;A&#39; + 5] || adj_mat[S[i] - &#39;A&#39; + 5][v]){
         v = S[i] - &#39;A&#39; + 5;
      }else{
         return false;
      }
      res[i] = v + &#39;0&#39;;
   }
   return true;
}
main() {
   char* str = "ABBECCD";
   if(petersonGraphWalk(str, str[0] - &#39;A&#39;) || petersonGraphWalk(str, str[0] - &#39;A&#39; + 5)){
      cout << res;
   }else{
      cout << -1;
   }
}

Output

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!