[kuangbin带我飞]专题二 搜索进阶

题解

HDU 2181：哈密顿绕行世界问题
题意：略
思路：
深度优先搜索，大概是当搜索到20的时候判断与此点联通的点是否是出发点，不能用vis的出发点判断，因为先前已经赋值为真了。
用领接矩阵储存。
代码：

#include <stdio.h>
#include <string.h>
bool g[21][21];
bool vis[21];
int tian[25];
int m;
int ans = 0;
void dfs(int st,int cnt)
{
    tian[cnt] = st;
    if (cnt == 20 && g[st][m])
    {
        tian[21] = m;
        ans++;
        printf("%d:  ",ans);
        for (int i = 1;i <= 20;i++)
            printf("%d ",tian[i]);
        printf("%d\n",tian[21]);
        return;
    }
    for (int i = 1;i <= 20;i++)
    {
        if (!vis[i] && g[st][i])
        {
            vis[i] = 1;
            dfs(i,cnt+1);
            vis[i] = 0;
        }
    }
    return;
}
int main()
{
    for (int i = 1;i <= 20;i++)
    {
        for (int j = 1;j <= 3;j++)
        {
            int x;
            scanf("%d",&x);
            g[i][x] = g[x][i] = 1;
        }
    }
    while (scanf("%d",&m) != EOF && m)
    {
        memset(vis,0,sizeof(vis));
        vis[m] = 1;
        dfs(m,1);
    }
    return 0;
}