C プログラムのピーターソン図の問題-C++-php.cn

C プログラムのピーターソン図の問題

PHPz

リリース： 2023-08-26 11:01:10

転載

899 人が閲覧しました

以下に示すようなグラフがあるとします。このグラフはピーターソン図です。頂点には 0 から 9 までの番号が付けられます。各頂点にはいくつかの文字があります。 L 個の頂点を使用して、このグラフ上で W を歩くことを考えます。ウォーキング W の文字列が S と同じ場合、文字列 S はウォーキング W によって実現されます。頂点を複数回訪問できます。

C プログラムのピーターソン図の問題

たとえば、文字列 S は「ABBECCD」に似ており、ウォーキング (0、1、6、9、7、2、3) によって実装されます。私たちの仕事は、そのようなウォークを見つけ、そのようなウォークが存在する場合、辞書編集上最小のウォークを見つけることです。そのような四球がない場合は、-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;
   }
}

ログイン後にコピー