题解：UVA291 The House Of Santa Claus

· · 题解

题目在这里 · UVA291 The House Of Santa Claus

题目简要：

就是一笔画画房子，但是要求你必须把所有路径都打印出来。

题意分析

就是给你一个房子图从点 1 开始再描一遍这个房子，描图不能有重边，输出描点的顺序，

暴力打表就能切过去，列举所有情况，再按照升序输出方案即可。

样例与题目无任何关系，不要看样例做题，他只是提示你要递增而已！

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"123153452\n123154352\n123451352\n123453152\n123513452\n123543152\n125134532\n125135432\n125315432\n125345132\n125431532\n125435132\n132153452\n132154352\n132534512\n132543512\n134512352\n134512532\n134521532\n134523512\n134532152\n134532512\n135123452\n135125432\n135215432\n135234512\n135432152\n135432512\n152134532\n152135432\n152345312\n152354312\n153123452\n153125432\n153213452\n153254312\n153452132\n153452312\n154312352\n154312532\n154321352\n154325312\n154352132\n154352312";
}//by·yutong_Seafloor

好吧其实以上打表做法只能娱乐而已，本题真正做法在下面。

分析

先把房子的图挂上来一点点分析

用深搜从一个点开始遍历，这个点必须是 1（题目给了自己回去看题目），我们先构边，开一个数组表示图：

m[1][2]=m[2][1]=1;//边1和边2一条边，以下同
m[1][3]=m[3][1]=1;
m[1][5]=m[5][1]=1;
m[2][3]=m[3][2]=1;
m[2][5]=m[5][2]=1;
m[3][4]=m[4][3]=1;
m[3][5]=m[5][3]=1;
m[4][5]=m[5][4]=1;

接着搜索，走过一条边以后标记成 0 代表这个边走过了，然后按照这条边接着往下走，直到把 8 条边走完了。

因为我们要走完 8 条边，所以特判数必须大于 8 才可以。

在走完一条遍历以后记得恢复初始数据不然会被误判。

代码（dfs版）

#include<bits/stdc++.h>
using namespace std;
int n,qwq[11];
bool yt[11][11];
void dfs(int a,int b)
{
    if(b>8)
    {
        for(int i=1;i<=8;i++)
        cout<<qwq[i];
        cout<<a<<"\n";
        return ;
    }
    qwq[b]=a;
    for(int i=1;i<=5;i++)
    if(yt[a][i])
    {
        yt[a][i]=yt[i][a]=0;
        dfs(i,b+1);
        yt[a][i]=yt[i][a]=1;
    }
    return ;
}
int main()
{
    yt[1][2]=yt[2][1]=1;
    yt[1][3]=yt[3][1]=1;
    yt[1][5]=yt[5][1]=1;
    yt[2][3]=yt[3][2]=1;
    yt[2][5]=yt[5][2]=1;
    yt[3][4]=yt[4][3]=1;
    yt[3][5]=yt[5][3]=1;
    yt[4][5]=yt[5][4]=1;
    dfs(1,1);
    return 0;
}//by·yutong_Seafloor