algorithm - 为什么此代码为 Petersen Graph(codechef) 提供 WA？

Question

我试图解决 Petersen Graph没有任何成功的问题。这段代码有什么问题？你可能会说这不是一个高效的解决方案，没关系。我在这里，对给定的图进行 DFS。

sruct ss 包含一个图。每个 String 都保存在一个 Set 中，每当递归终止时都会产生一个输出。我找不到这种方法失败的测试用例。你能给我一个这种方法会失败的测试用例吗？

#include<bits/stdc++.h>
using namespace std;
struct ss{
int p;
int a[3];
char s[3];
};
string get(int k){
switch(k){
case 0:return "0";
case 1:return "1";
case 2:return "2";
case 3:return "3";
case 4:return "4";
case 5:return "5";
case 6:return "6";
case 7:return "7";
case 8:return "8";
case 9:return "9";
}
}
void traverse(string s,ss z[10],int index, set<string> &s1,string s2,int v){
int p = s[index]-'A',i,j;
if(v!=-1)s2 +=get(v);
if(!s[index]){
    s1.insert(s2);
    return;
}
if(v==-1){
    traverse(s,z,index+1,s1,s2,z[2*p].p);
    traverse(s,z,index+1,s1,s2,z[2*p+1].p);
}
else{
if(v>=5){v = v-5;v = 2*v+1;}
    for(i=0;i<3;i++){
        if(z[v].s[i]==s[index]){
           traverse(s,z,index+1,s1,s2,z[v].a[i]);
           break;
        }
    }
    for(j=0;j<3;j++){
       if(z[v].s[j]==s[index]){
           traverse(s,z,index+1,s1,s2,z[v].a[j]);
           break;
        }
    }
}
}
int main(){
    string s;
    set<string> s1;
    int t;
    ss z[ ]={
        {0,{1,4,5},{'B','E','A'}},
        {5,{0,7,8},{'A','C','D'}},
        {1,{0,2,6},{'A','C','B'}},
        {6,{1,8,9},{'B','D','E'}},
        {2,{1,3,7},{'B','D','C'}},
        {7,{2,5,9},{'C','A','E'}},
        {3,{2,4,8},{'C','E','D'}},
        {8,{3,5,6},{'D','A','B'}},
        {4,{0,3,9},{'A','D','E'}},
        {9,{4,6,7},{'E','B','C'}}
        };
    cin>>t;
    while(t--){
         s1.clear();
        cin>>s;
        traverse(s,z,0,s1,"",-1);
        if(s1.end()==s1.begin()){
            cout<<-1<<"\n";
        }
        else
            cout<<*s1.begin()<<"\n";
    }
}

Answer 1

代码几乎在我尝试的每个测试用例中都失败了。我认为问题出在 traverse 中，在 for 循环中的 if 语句条件中(行 45 和 51)。

if(z[v].s[i]==s[index])

在这里，您需要索引 x，这样 z[x].p 等于 v。 v 并不总是正确的索引，因此 z[v] 是不正确的。另一行也是如此。尝试测试用例“EE”和“ABCD”。

我认为按照 Z[i].p 值的顺序重新排列 Z 数组是最简单的。