C - 哈密顿绕行世界问题——DFS

超、凢脫俗 2022-06-15 04:16 152阅读 0赞

Think:  
1DFS:  
1>控制结束条件  
2>传递  
2反思:  
1>不自信  
2>未判断最后一个城市是否可以到达初始出发城市（感谢鑫哥点拨）  
3收获:  
1>DFS加深理解  
2>通过宏观分步调试判断出现错误地方  
3>哈密顿图理解:不重复经过每个结点回到最初出发结点

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    struct node
    {
        int t[4];
        int front;
    } a[24];
    
    int m, k, cnt, v[24];
    
    void Input();
    void DFS(int x);
    
    int main()
    {
        Input();
        while(scanf("%d", &m) && m)
        {
            k = cnt = 0;
            memset(v, 0, sizeof(v));
            a[m].front = -1;
            v[m] = 1, cnt++;
            DFS(m);
        }
        return 0;
    }
    void DFS(int x)
    {
        int i;
        if(cnt == 20)
        {
            int flag = 0;
            for(i = 1; i <= 3; i++){
                if(a[x].t[i] == m){
                    flag = 1;
                    break;
                }
            }
            if(!flag)
                return;
            int tp, link[24];
            tp = 0;
            link[tp++] = m;
            link[tp++] = x;
            int c = a[x].front;
            while(c != -1)
            {
                link[tp++] = c;
                c = a[c].front;
            }
    
            k++;
            printf("%d: ", k);
            for(i = tp-1; i >= 0; i--)
                printf(" %d", link[i]);
            printf("\n");
        }
        else
        {
            for(i = 1; i <= 3; i++)
            {
                if(v[a[x].t[i]] == 0)
                {
                    cnt++;
                    a[a[x].t[i]].front = x;
                    v[a[x].t[i]] = 1;
                    DFS(a[x].t[i]);
                    cnt--;
                    v[a[x].t[i]] = 0;
                }
            }
        }
    }
    void Input()
    {
        for(int i = 1; i <= 20; i++)
        {
            for(int j = 1; j <= 3; j++)
            {
                scanf("%d", &a[i].t[j]);
            }
        }
    }

[vjudge]: https://vjudge.net/contest/161869#problem/C