C 프로그램의 Peterson 다이어그램 문제

아래와 같은 그래프가 있다고 가정해 보겠습니다. 이 그래프는 피터슨 다이어그램입니다. 정점에는 0부터 9까지 번호가 매겨져 있습니다. 각 꼭지점에는 문자가 있습니다. L 정점을 사용하여 이 그래프에서 W 걷기를 생각해 보세요. 걷기 W의 문자 순서가 S와 같을 때 문자열 S는 걷기 W로 구현됩니다. 정점을 여러 번 방문할 수 있습니다.

예를 들어 문자열 S는 걷기(0, 1, 6, 9, 7, 2, 3)를 통해 달성되는 "ABBECCD"와 유사합니다. 우리의 임무는 그러한 걷기를 찾는 것이고, 그러한 걷기가 존재한다면 사전순으로 가장 작은 걷기를 찾는 것입니다. 그러한 걷기가 없으면 -1이 반환됩니다.

Algorithm

petersonGraphWalk(S, v) -

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

의 중국어 번역은 다음과 같습니다.

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

위 내용은 C 프로그램의 Peterson 다이어그램 문제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!