โจทย์ Peterson Graph ในโปรแกรม C

สมมติเรามีกราฟแบบด้านล่าง นั่นคือ Peterson Graph จุดยอดหมายเลข 0 ถึง 9 แต่ละจุดยอดมีตัวอักษรบางตัว ให้พิจารณาการเดิน (Walk) W ในกราฟนี้ ที่ใช้จุดยอด L จุด สตริง S ที่มีตัวอักษร L ตัว ถูก realized โดยการเดิน W เมื่อลำดับตัวอักษรใน W และ S เหมือนกัน เราสามารถเยี่ยมจุดยอดซ้ำได้

เช่น สตริง S = "ABBECCD" สามารถ realized ได้โดยการเดิน (0, 1, 6, 9, 7, 2, 3) งานของเราคือหาการเดินแบบนั้น และถ้ามี ให้หาการเดินที่น้อยที่สุดในระดับ Lexicographical ถ้าไม่มี ให้คืน -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++){
        // ตรวจสอบ outer graph
        if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
            v = S[i] - 'A';
        }
        // ตรวจสอบ 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