假設我們有一個如下所示的圖形。這個圖形是彼得森圖。頂點從0到9編號。每個頂點都有一些字母。考慮一個在該圖中的行走W,其中使用了L個頂點。當行走W中的字母序列和S相同時,字串S由行走W實現。我們可以多次訪問頂點。
例如,一個字串S類似於“ABBECCD”,這由行走(0, 1, 6, 9, 7, 2, 3)實現。我們的任務是找到這樣的行走,如果存在這樣的行走,則找到字典順序最小的行走。如果沒有這樣的行走,則回傳-1。
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
#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
以上是C程序中的Peterson圖表問題的詳細內容。更多資訊請關注PHP中文網其他相關文章!