Rumah > Artikel > pembangunan bahagian belakang > Masalah rajah Peterson dalam program C
Andaikan kita mempunyai graf seperti yang ditunjukkan di bawah. Graf ini ialah gambar rajah Peterson. Bucu dinomborkan dari 0 hingga 9. Setiap bucu mempunyai beberapa huruf. Pertimbangkan berjalan W pada graf ini menggunakan bucu L. Apabila urutan huruf dalam berjalan W adalah sama dengan S, rentetan S direalisasikan dengan berjalan W. Kita boleh melawati puncak beberapa kali.
Sebagai contoh, rentetan S serupa dengan "ABBECCD", yang dilaksanakan dengan berjalan kaki (0, 1, 6, 9, 7, 2, 3). Tugas kami adalah untuk mencari jalan-jalan seperti itu dan, jika jalan-jalan sedemikian wujud, cari jalan-jalan terkecil dari segi leksikografi. Jika tiada jalan seperti itu, -1 dikembalikan.
petersonGraphWalk(S, v) - Terjemahan bahasa Cina bagi
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; } }
Atas ialah kandungan terperinci Masalah rajah Peterson dalam program C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!