DFS || HDU 2181

题意：一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。

前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出

输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市

dfsdfsdfsdfsdfsdfs…………

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

#define SZ 2010

bool vis[];

int path[];

struct node

{

    int a, b, c;

}city[];

int ct[][];

int cnt = ;

int m;

void dfs(int x, int k)

{

    path[k] = x;

    for(int i = ; i <= ; i++)

    {

        int t = ct[x][i];

        if(t == m && k == )

        {

            cnt++;

            printf("%d: ", cnt);

            for(int i = ; i < ; i++) printf(" %d", path[i]);

            printf(" %d\n", m);

            return;

        }

        if(t == m) continue;

        if(!vis[t])

        {

            vis[t] = ;

            dfs(t, k+);

            vis[t] = ;

        }

    }

}

int main()

{

    for(int i = ; i <= ; i++)

        for(int j = ; j <= ; j++)

            scanf("%d", &ct[i][j]);

    for(int i = ; i <= ; i++) sort(ct[i]+, ct[i]+);

    while(true)

    {

        scanf("%d", &m);

        if(m == ) break;

        cnt = ;

        memset(vis, , sizeof(vis));

        vis[m] = ;

        dfs(m, );

    }

    return ;

}

巴特西

DFS || HDU 2181

最新文章

热门文章